Complexity Theory - Winter 2004/5
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:
- 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
HANDOUTS:
- 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