Oded Goldreich - Current Teaching
Introduction to Complexity Theory
In 2017-18, I will supervise a (year long) reading group on
Introduction to Complexity Theory.
Due to the students' requests, there will be two groups,
which will meet at different times and places.
Interested students should contact the group leader regarding details.
- A group led by Gal Arnon (email email@example.com)
will meet on Tuesdays (starting Oct-31) between 11 and 13,
at room 108 (of Bldg II).
- A group led by Uri Ben-Levy (email firstname.lastname@example.org)
will meet on Thursdays (starting Nov-2) between 12 and 14,
at room 208 (of Bldg II).
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.
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 lent (beyond those in the library).
A general suggested outline for the reading will be provided by me
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.
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.
- revisiting the P-vs-NP Question and NP-Completeness;
- separation results for time and space complexity;
- non-uniform complexity (e.g., P/poly);
- the Polynomial-time Hierarchy;
- space complexity (focus on log-space and NL);
- the class #P and approximate-#P;
- randomized computations (RP and BPP);
- probabilistic proof systems (IP, ZK, and PCP);
- pseudorandomness (generators and derandomization);
- approximation (optimization/search and property-testing/decision);
- average-case complexity;
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.