To: Bibliography and references
Homework
Handouts and Slides

Instructor: Moni Naor

Grader: Asaf Nussbaum

When: Thursday 14:00--17:00

Where: Ziskind 1

**DESCRIPTION: **
Computational complexity studies the inherent resources needed to
perform various computational tasks. Typical resources are time and
memory, but
other measures are of interest as well, such as parallelism,
communication and randomness. The goal of the course is to provide a
firm foundation
of the field.

**PREREQUISITES:** Students
are expected to be familiar with algorithms, data structures,
probability theory, and linear algebra, at an *undergraduate*
level; a basic course in computability is assumed.

**METHOD OF EVALUATION:**
There will be around ten homework assignments and a final test.
Homework assignments should be turned in on time (usually* two weeks*
after
they are given)! Try and do as many problems from each set. You may
(and
are encouraged to) discuss the problems with other students, but the
write-up
MUST be individual.

**Exam :** The exam will be
in class.

**BIBLIOGRAPHY:** There is no textbook for the course. A lot of background and
relevant
material is available in

- Christos Papadimitriou ,
*Computational Complexity*, Cambridge, 1994

- Michael Sipser,
*Introduction to the Theory of Computation*, 1997

- Garey and Johnson.
*Computers and Intractability: A Guide to the Theory of NP-Completeness*. New York: W. H. Freeman, 1979.

Online courses close in nature to our course:

**Lecturers**: Steven Rudich and Avrim Blum, Computational Complexity Theory,**University**: CMU. link**Lecturer**: Luca Trevisan, Computational Complexity,**University**: UC Berkeley. link

**Lecturer**: Oded Goldreich, Computational Complexity,**University**: Weizmann. link

**Lecturer**: Chris Umans, Complexity Theory,**University**: Caltech. link

**Lecturer**: Sanjeev Arora , Computational Complexity Theory,**University**: Princeton . link

Bibliography on specific topics (communication complexity, randomization):

- E. Kushilevitz and N. Nisan, Communication
Complexity, Cambridge 1997.

- N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley, 1992.
- R. Motwani and P. Raghavan,
Randomized Algorithms, Cambridge 1995.

Important Web Resources on Complexity:

- Electronic Colloquium on Computational Complexity (ECCC), An Online repository of papers on the subject: link to ECCC
- Lance Fortnow's Computational Complexity Web Log, updated almost
daily with news, reviews and views, link

- Scott Aaronson's Complexity Zoo, "The sprawling web of known
relations among complexity classes", link to the zoo

- Homework 1. Due Nov
4th. ps
- Homework 2. Due Nov 11th. ps
- Homework 3. Due Nov 18th. ps
- Homework 4. Due Dec 2nd. ps
- Homework 5. Due Dec 9th. ps
- Homework 6. Due Dec 16. ps
- Homework 7. Due Dec 30. ps
- Review Homework no due date yet 30. ps

- Lecture 1:
Introduction, Communication Complexity. pps
- Lecture 2:
Communication Complexity - non-deterministic and probabilistic pps
- Lecture 3: Space
Complexity pps
- Lecture 4:
Probabilistic Space and Time Classes pps
- Lecture 5:
Probabilistic Time Classes, Branching Programs and Alternation pps
- Lecture 6: Polynomial
Time Hierarchy pps
- Lecture 7: Hardness of
Unique SAT, #P-Completeness of the Permanent,
Testing by low memory devices
pps
- Lecture 8: Toda's Theorem,
Hardness of the Permanent on the Average, Interactive Proofs
pps
- Lecture 9:
The Power IP, Arthur-Merlin Games and their power
pps
- Lecture 10:
Statistical Zero-Knowledge, Deniable Authentication, AM Protocols for VC,
Hardness and Randomness.
pps
- Lecture 11:
Hardness and Randomness, the NW Generator, Semi-Random Sources, The Trevisan
Extractor.
pps
- Lecture 12:
Hardness Amplification, Strong Error Reduction via Extractors, Definition of NC,
Lower bound for formulas.
pps
- Lecture 13:
P-Completeness,
Communication Complexity Characterization of Depth, ST-Connectivity Lower Bound
pps
- Lecture 14:
Lower bound for parity via the Switching Lemma, Permutation Branching Programs
pps
- Lecture 15:
Natural Proofs, Propositional Proof Complexity
pps