Gisp proposal: Advanced Topics in The Theory of Computation
Download 17.02 Kb.
|
- Navigate this page:
- 2. Syllabus Week 1 (Jan 24 th -26 th ). How can you represent a computer mathematically
- Week 2 (Jan 29 th -Feb 2 nd ). A powerful technique for proving the limits of computing.
- Week 3 (Feb 5th-Feb 9 th ).
- Week 5 (Feb 19 th -Feb 23 rd ). Further Results in Time and Space Complexity.
- Week 7 (Mar 5 th -Mar 9 th ). Alternation.
- Week 9 (Mar 19 th -Mar 23 rd ). Introduction to Cryptography.
- Week 11 (Apr 9 th -Apr 13 th ). More on the power of Interactive Proofs.
- Week 13 (Apr 23 rd -Apr 26 th ). Pseudorandomness.
| GISP Proposal:
Advanced Topics in The Theory of Computation Semester II, 2000-2001 1. The focus of many of the courses in the computer science department at Brown is on learning to build robust software with today’s computers. Consequently, computer science is often viewed as simply an engineering discipline. While computer engineering is an important and worthwhile field of study in its own right, very little attention is given to the theoretical underpinnings of computer science. The theory of computation attempts to answer deep questions, concerning not just how to compute things, but the nature of the things that are computable. Some problems are simply not tractable by computational means. The algorithms that solve them either do not terminate, or are hopelessly slow. What types of problems are impossible to solve on a computer? What types of problems are “hard” to solve on a computer? Can we somehow make the “hard” problems less difficult to solve? Or can we prove that the difficulties are inherent in the problems? For many types of problems, these questions remain unanswered, and are at the forefront of current research in mathematics and computer science. Such questions are of the utmost practical importance, for many of the problems investigated have direct applications to cryptography and optimization software. However, the theory of computation is valuable not only for its practical importance, but also for its philosophical importance, mathematical beauty, and intellectual challenge. The goal of this GISP is to survey some advanced topics in the theory of computation. These topics are not covered by other courses in the computer science curriculum. The computational emphasis of the course will not be on implementational details, but rather on the mathematical truths implied by the computational models. It is hoped that the participants of this GISP will gain a greater appreciation for the profundity of the questions currently posed by the theory of computation, and the elegance and creativity of the mathematical methods employed to solve them. 2. Syllabus
Turing Machines are presented as our standard model of computation. Various other models are shown to be equivalent to the Turing Machine (Sipser, chapter 3).
The “halting” problem, a famous problem that is “too hard” for any computer, is presented. Particular emphasis is paid to the method of proof, “diagonalization.” Later this method will be shown insufficient for proving an open problem in the field (Sipser, chapter 4).
The Recursion theorem. Undecidability of Logical Theories (Sipser, Chapter 6).
The time complexity classes P and NP, and the space complexity classes PSPACE, L, and NL are reviewed. Examples are given of problems in each class. The notion of “complete” problems for NP, PSPACE, and NL is presented. The notion of a reduction is also presented (Sipser Ch 7 & 8).
The proof of an NP complete problem. Proof that CoNL = NL (Sipser Ch 7 & 8).
The hierarchy theorems are presented. The notions of oracles and relativization are introduced. Proof is given to show that diagonalization is not enough to prove P different than NP (Sipser, 9.1-2).
Alternating Turing machines and the polynomial hierarchy are introduced, and elementary results are given (Sipser 10.3).
Randomized complexity classes. The class BPP is introduced (Sipser 10.2).
Mathematical Foundations of Cryptography (Goldreich, Chapter 1). Spring Recess (Mar 24th-Apr 1st)
Definitions and examples of Interactive and Zero-Knowledge proofs are given (Goldreich, Chapter 2.1, 3.1).
IP=PSPACE (Goldreich, Chapter 2.2).
Definition of probabilistically checkable proofs, and relation to approximation algorithms (Goldreich, Chapter 2.4).
Definitions of randomness. The complexity theorists approach to defining randomness. Examples and open problems (Goldreich, Chapter 3.1-3.4, 3.7). Reading Period (Apr 27th-May 8th) Final Paper Due, accompanied by short presentation. 3. Bibliography Sipser, Michael. Introduction to the Theory of Computation. Boston: PWS Publishing Company, 1997. Goldreich, Oded. Modern Cryptography, Probabilistic Proofs, and Pseudorandomness (Algorithms and Combinatorics, Vol 17). Springer Verlag, 1997. Note: We also have for our reference an author’s copy of the soon to be published second edition of Oded Goldreich’s book. Permission has been granted for the reproduction of this edition for educational purposes. 4. The members of the GISP intend to meet approximately three hours per week, in the form of three weekly meetings. Two of the weekly meetings will be devoted to the presentation of new material. One or two members of the GISP will be assigned the task of leading the presentation each week. The presenter(s) will also be responsible for selecting a set of problems corresponding to the material presented. Our faculty sponsor will attend at least one of the presentations each week in order to assess participation, as well as to offer the occasionally required expertise. The third weekly meeting will be a problem solving session. During this time, the presenter(s) for the week will explain the answers to the problems they assigned, and we will record each other’s performance, for the review of our faculty sponsor. We will also use this time to discuss particularly difficult problems, as well as general techniques. Although there will not be a regularly scheduled meeting time for sub-groups to convene, it is expected that the members of the GISP will often meet in sub-groups in order to collaborate on problems. 5. In the planning of the GISP, we have primarily consulted with Professor Eli Upfal. 6. The GISP will not require funding. The only necessary materials are the course texts, which students will purchase individually. 7. Student comprehension and performance will be evaluated on the basis of three different measures: completion of weekly problem sets, quality of presentations, and a final research paper.
8. The principal authors of this proposal are Kevin Matulef, Steve Canon, and Harry Li. Kevin Matulef was responsible for organizing many of the topics into a viable syllabus. Steve Canon and Harry Li also assisted in planning the syllabus, as well as the structure of the course. We consulted with our faculty sponsor, Professor Eli Upfal, both before and after drafting a proposal. He provided constructive criticism regarding the syllabus, and helped to focus our interests into a one-semester course. Finally, all members of the GISP met both before and after drafting a proposal, in order to discuss the goals of the project, and to insure that we had plans for accomplishing those goals. 9. The majority of the material in this course is not covered by any course at Brown. There are two existing courses, Models of Computation (CS51) and Computational Complexity (CS159), which contain slightly overlapping material, but not nearly enough to constitute undue duplication of a course. The overlap with CS51 has been strictly confined to weeks one, two, and parts of four and five. It is intended only for purposes of review, and for the establishment of a firm foundation. The latter topics in the GISP will go well beyond the material in CS51, and it is expected that the members of the GISP will have CS51 or the equivalent before the start of the semester. The material in CS159 also only overlaps slightly with this GISP, in weeks 4 and 5 on the topic of space complexity. Indeed, the syllabus of this GISP was specifically designed to cover many of the topics that are omitted in CS159, and it is expected that students may receive the most benefit from enrolling in both courses. 10. Not Applicable 11. Although many students have expressed interest in this course, and have desired to be a part of the planning process, we expect that only around 10 students will take it. There will be ample opportunity for discussions during the presentation of new material, and also for collaboration on the weekly problem sets. Directory: courses courses -> Algorithms for Register Allocation Andrew Pardoe courses -> Ieor 4600 Mixed-Integer Rounding Inequalities courses -> San José State University Social Science/Psychology Psych 175, Management Psychology, Section 1, Spring 2014 courses -> Kennan's Telegram (Excerpt) courses -> The university of british columbia courses -> A hurricane track density function and empirical orthogonal function approach to predicting seasonal hurricane activity in the Atlantic Basin Elinor Keith April 17, 2007 Abstract courses -> Cover page need figure & title by Proposed Table of Contents courses -> Objectives courses -> Dr. Jeff Masters' WunderBlog Download 17.02 Kb. Share with your friends:
|