Oded Goldreich - Current Teaching


Introduction to Complexity Theory

In 2017-18, I will supervise a (year long) reading group on Introduction to Complexity Theory. The first meeting will take place on Tuesday, 31-Oct-17, at 14:15-16:00, in Room B of FGS building.

This is a full-year student-led reading group in Introduction to Complexity Theory. It is intended for a small group of highly motivated students, who wish to learn the subject in depth as well as experiment with reading material by themselves and brainstorming with other students.

FORMAT

The reading will be based on my book on Computational Complexity, and is expected to cover approximately half the material in that book. The students will get free access to an e-copy of the book, and several hard copies can be lended (beyond those in the library).

A general suggested outline for the reading will be provided by me (see HERE), but the actual implementation will be up to the students.

My suggestion, which was implemented in past years, is that the students will read 10-20 pages a week, and participate in a weekly meeting (of 2 hours). In the meeting the students will discuss the material they read, focusing on resolving difficulties by themselves. I will be happy to attend some of the meetings, and answer various questions or present some material, all at the students' choice.

Participating students will be credited 2 points for each semester.

SYLLABUS

Complexity Theory is concerned with the study of the intrinsic difficulty of computational tasks. This study tend to aim at generality: It focuses on natural computational resources, and the effect of limiting those on the class of problems that can be solved.

The (half-century) history of Complexity Theory has witnessed two main research efforts (or directions). The first direction is aimed towards actually establishing concrete lower bounds on the complexity of problems, via an analysis of the evolution of the process of computation. Thus, in a sense, the heart of this direction is a ``low-level'' analysis of computation. Most research in circuit complexity and in proof complexity falls within this category. In contrast, a second research effort is aimed at exploring the connections among computational problems and notions, without being able to provide absolute statements regarding the individual problems or notions. This effort may be viewed as a ``high-level'' study of computation, and the book is focused on it. Specific topics include:

My complexity theoretic book has some overlap with my book on Foundations of Cryptography. Specifically, one-way functions, pseodorandom generators, and zero-knowledge proofs are covered in both books, but the perspective and the actual contents are different.

PREREQUISITES

There are no formal prerequisites for the course, but comfortable familiarity with the notion of an algorithm is definitely assumed. Students who did not take a course in "computability" (or "theory of computation") or are not sure about it, should study Section 1.2 in the book. This section discusses the notion of computational tasks and algorithms, while emphasizing the importance of representation.


Record of past teaching (partial)


Back to homepage.