A two-semester supervised reading on Complexity Theory
Oded Goldreich
Currently given (2022-23).
Given in the same (supervised reading) format
in 2012-2013, 2014-15, 2016-17, 2017-18, 2018-19, 2020-21 and 2021-22
(previously given in a regular course format
in 2005-06, 2007-08, and 2009-10).
Introduction to Complexity Theory:
A Two-Semester Supervised Reading Group
A general suggested outline for the reading is provided by me
(see HERE),
but the actual implementation will be up to the students.
In a nutshell, Complexity Theory means the study of the limitation
of efficient computation.
Format (starting 2017-18)
This reading group is relatively demanding, intended for 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.
It spans two semesters and requires reading 10-20 pages per week
as well as participation in weekly meetings
in which the reading material will be discussed.
The meetings are student-run, but I will be happy to join meetings
that cover more challenging material upon request from the students;
in the past, I have joined 2-4 meetings each semester.
The reading will be based on my
book on Computational Complexity,
and will 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 suggested outline for the reading is provided
in the webpage oded/cc-gl.html,
but the actual implementation will be up to the students.
Based on previous years,
my suggestion is to form a group of 4-6 students,
and use multiple groups if demand is high enough.
Participating students will be credited 2 points for each semester,
where a pass grade will be given subject to submitting (light-weight)
homework assignments that are marked as satisfactory.
Format (before 2017-18)
The course will be based on my
book on Computational Complexity,
and will cover approximately half the material in that book.
Students will be expected to read 10-20 pages a week,
and to participate in a weekly meeting (of 1-2 hours).
Each meeting will consist of two parts.
In the 1st part, we will discuss the material read,
and I will answer questions and/or add clarifications.
In the 2nd part, I will motivate and/or provide an overview
for the material to be read in coming week.
(The students will get free access to an e-copy of the book.)
Participating students will be credited 2 points for each semester,
where a pass grade will be given subject to submitting (light-weight)
homework assignments that are marked as satisfactory.
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 course will be confined to it. Specific topics will include:
- 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 systesms (IP, ZK, and PCP);
- pseudorandomness (generators and derandomization);
- approximation (optimization/search and property-testing/decision);
- average-case complexity;
This course has some overlap with the course
Foundations of Cryptography.
Specifically, one-way functions, pseodorandom generators,
and zero-knowledge proofs are covered in both courses,
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.
The actual teaching as it took place in 2005-06
- The P-vs-NP Question (in search and decision forms),
the notion of a reduction.
See
A
brief overview to Complexity Theory (a teaser) and
The
preliminaries - computational tasks and model.
- Optimization problem, self-reducibility,
the existence of NP-complete problems, CSAT is in NPC.
See
On Teaching the Basics of Complexity Theory.
- SAT is in NPC, NPI (i.e., $NP-(P+NPC)$),
promise problems, optimal search algorithms, $NP \cap coNP$.
See
Four
Advanced Topics Related to NP and NPC.
- On P/poly and PH.
(See
notes.)
- cont. of last lecture + hierarchy and gap theorems.
See
More
resources, more power?
- Space Complexity (part 1: the mind-set and log-space):
See
notes.
- Space Complexity (part 2: NL and PSPACE):
See same
notes.
- Ending space complexity and starting randomized computations.
See notes on
Randomized
Complexity Classes
- Randomized Complexity Classes (cont.):
See same
notes.
- Exact Counting and Approximate Counting (via reduction to NP):
See
notes.
- Two topics: (1) On the Complexity of Unique Solutions,
and (2) Uniform Generation and its relation to Approximate Counting.
See
notes.
- Two unrelated topics:
(1) Reducing Uniform Generation to NP, and (2) One-Way Functions.
See, respectively, sections 6.2.4.2 and 7.1 in the
3rd part
of my draft (of a book).
- Worst-case hardness and average-case hardness:
See Section 7.2 (and 7.1.3) in the
3rd part
of the said draft.
- Pseudorandomness: general-purpose generators.
See (mainly) Section 8.3 in the
4th
part of the said draft.
- Pseudorandomness: derandomization.
See (mainly) Section 8.4 in the
4th
part of the said draft.
- Probabilistic proof systems: IP.
See Section 9.1 in the
4th
part of the said draft.
- Probabilistic proof systems: PCP.
See Section 9.3 in the
4th
part of the said draft.
Focus on Sections 9.3.1, 9.3.2.0 and 9.3.2.1.
- PCP and approximation problems.
See Sections 9.3.4 and 10.1.1 in the said draft.
- Average-case complexity.
See Section 10.2 in the
5th
part of the said draft.
Back to homepage.