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

  1. Week 1 (Jan 24th-26th). How can you represent a computer mathematically?

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).

  1. Week 2 (Jan 29th-Feb 2nd). A powerful technique for proving the limits of computing.

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).

  1. Week 3 (Feb 5th-Feb 9th).

The Recursion theorem. Undecidability of Logical Theories (Sipser, Chapter 6).

  1. Week 4 (Feb 12th-Feb 16th). Review of Computational Complexity.

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).

  1. Week 5 (Feb 19th-Feb 23rd). Further Results in Time and Space Complexity.

The proof of an NP complete problem. Proof that CoNL = NL (Sipser Ch 7 & 8).

  1. Week 6 (Feb 26th-Mar 2nd). Proving Problems to be Intractable.

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).

  1. Week 7 (Mar 5th-Mar 9th). Alternation.

Alternating Turing machines and the polynomial hierarchy are introduced, and elementary results are given (Sipser 10.3).

  1. Week 8 (Mar 12th-Mar 16th). Randomness complicates the world of Complexity.

Randomized complexity classes. The class BPP is introduced (Sipser 10.2).

  1. Week 9 (Mar 19th-Mar 23rd). Introduction to Cryptography.

Mathematical Foundations of Cryptography (Goldreich, Chapter 1).

Spring Recess (Mar 24th-Apr 1st)

  1. Week 10 (Apr 2nd-Apr 6th). Games of verifying information: Introduction to Probabilistic proofs.

Definitions and examples of Interactive and Zero-Knowledge proofs are given (Goldreich, Chapter 2.1, 3.1).

  1. Week 11 (Apr 9th-Apr 13th). More on the power of Interactive Proofs.

IP=PSPACE (Goldreich, Chapter 2.2).

  1. Week 12 (Apr 16th-Apr 20th). Probabilistically Checkable Proofs.

Definition of probabilistically checkable proofs, and relation to approximation algorithms (Goldreich, Chapter 2.4).

  1. Week 13 (Apr 23rd-Apr 26th). Pseudorandomness.

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.

  • Performance on problem sets will be evaluated weekly. At the end of each of the problem solving sessions, we will record who has completed that week’s assignment. Our faculty sponsor will retain these records, as well as the written assignments, to occasionally verify that no student has fallen behind.
  • As stated earlier, we will rotate the duty of presenting new material each week. It is expected that the presentations will be clear, well researched summaries of a particular topic. The presenter for each week will also be responsible for accompanying their presentation with written notes, both for evaluation purposes, and for the preservation of the course for future students.
  • The final research paper will be approximately 5-10 pages long. It is not expected that the research paper comprise original work. More likely, it will highlight a particular topic or proof not covered during the semester. Another feasible research topic will be the compilation and clear presentation of open problems in the field. The research paper will be due during reading period. Each student will give a small presentation of their research topic to the rest of the class and our faculty sponsor during this time.

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.