Computational Complexity

• Madhu Sudan
  Foundations and Trends® in Theoretical Computer Science
  [Info] [Topics]
  The growth in all aspects of research in the last decade has led to a multitude of new publications and an exponential increase in published research. Finding a way through the excellent existing literature and keeping up to date has become a major time-consuming problem. Electronic publishing has given researchers instant access to more articles than ever before. But which articles are the essentials one that should be read to understand and keep abreast with developments of any topic? To address this problem Foundations and Trends® in Theoretical Computer Science will publish high-quality survey and tutorial monographs of the field using modern techniques to enable both instant linking to the primary research in its electronic form and affordable paper copies, finally delivering on the promise to authors of multiple channel publishing from a single source.
  Editor-in-Chief: Madhu Sudan
  

• The P-versus-NP page
  
• Colloquium on Computational Complexity
  
• Lance Fortnow's complexity blog and his selected survey talks.
• Theory of Computing Blog Aggregator
• Complexity Zoo
• A Short History of Computational Complexity by Lance Fortnow and Steve Homer
• Computational Complexity: A Modern Approach , book draft by Sanjeev Arora and Boaz Barak
• Computational Complexity: A Conceptual Perspective , a book written by Oded Goldreich
• Some lecure notes on SAT, flow problem,linear programming,universal hashing

• Madhu Sudan
  Advanced Complexity Theory (MIT 6.841)
  [Info] [Topics]
  This course is a follow-up to Introduction to the theory of computation (6.840). It covers advanced topics in computational complexity, leading up to the state-of-the-art in the field. Principal topics include:

  1. Review of time and space complexity
  2. Non-determinism and alternation
  3. Non-uniform models of computation and lower bounds
  4. Interaction, proof, and knowledge
  5. Probabilistically checkable proofs and inapproximability
  6. Quantum computation
  Date: Spring 2009
  Lecturer: Madhu Sudan
  

• Luca Trevisan
  CS 278 -- Computational Complexity
  [Info] [Topics]
  This course will roughly be divided into two parts: we will start with "basic" and "classical" material about time, space, P versus NP, polynomial hierarchy and so on, including moderately modern and advanced material, such as the power of randomized algorithm, the complexity of counting problems, and the average-case complexity of problems. In the second part, we will focus on more research oriented material, to be chosen among: (i) PCP and hardness of approximation; (ii) lower bounds for proofs and circuits; and (iii) derandomization and average-case complexity.
  Semester: Spring 2008
  Lecturer: Luca Trevisan
  
• Jin-Yi Cai
  CS810: Introduction to Complexity Theory (Models and Formalisms of Computation)
  [Info] [Topics]
  We will start with a review of some topics from a typical undergraduate course in Theory of Computing, including such concepts as Turing machines, recursive functions, computability and incomputability, and the Church-Turing thesis.
  We then consider time and space bounded computation; deterministic and non-deterministic time classes and space classes, LOGSPACE, NL, P, NP, PSPACE, etc; Savitch's theorem, Immerman-Szelepcsenyi Theorem, Cook-Levin Theorem, NP-completeness and P-completeness, Karp's problems. We will also introduce randomized complexity classes ZPP, RP, BPP; polynomial time hierarchy; Sipser-Lautemann Theorem, interactive proofs, Arthur-Merlin Games, LFKN protocol and Shamir's Theorem (with a proof by Shen, using "diagram chasing"), probabilistically checkable proofs; non-uniform complexity, Karp-Lipton Theorem, graph non-isomorphism problem; circuit lower bounds, bounded depth circuits; Counting problems and Valiant's theory, Permanent and determinant problem. If time permit we may also discuss other topics such as pseudorandom generators and hardness versus randomness, or dichotomy theorems.
  
  Date: Fall 2008
  Level: First year graduate
  Lecturer: Jin-Yi Cai
  Comment: The course notes are clear.
  

• Salil Vadhan
  CS 225: Pseudorandomness
  [Info] [Topics]
  The course will reach the cutting-edge of current research in this area, covering some results from within the last year. At the same time, the concepts we will cover are general and useful enough that hopefully anyone with an interest in the theory of computation or combinatorics could find the material appealing.

  • The Power of Randomness
  • Basic Derandomization Techniques
  • Expander Graphs
  • Randomness Extractors
  • List-Decodable Error-Correcting Codes
  • Pseudorandom Generators
  • Potential Additional Topics
  Semester: Spring 2007
  Prerequisites: Theory of Computation
  Level: Graduate
  Lecturer: Salil Vadhan
• Boaz Barak
  CS 522 Computational Complexity
  [Info] [Topics]
  • Derandomization
  • Expanders and extractors
  • Reingold's deterministic O(log n)-space algorithm for undirected s-t connectivity
  • PCP theorem
  • List-Decodable Error-Correcting Codes
  • Pseudorandom Generators
  • Potential Additional Topics
  Semester: Spring 2007
  Level: Graduate
  Lecturer: Boaz Barak

• Dominique Unruh, Joint Advanced Student School(JASS)
  Course 1: Proofs and Computers
  [Info] [Topics]
  • Introduction to Complexity Theory
  • Randomness and Non-Uniformity
  • Hierarchy Theorems
  • Valiant-Vazirani Lemma
  • Toda's Theorem, Part I
  • Toda's Theorem, Part II
  • Interactive Proofs
  • #P. Complexity of the Permanent. An interactive Proof for P^{#P}
  • Circuit Complexity
  • Probabilistically Checkable Proofs
  • PCP Theorem by Gap Amplification
  Date: April 2 through April 12, 2006
  

• Luca Trevisan
  CS 294 Pseudorandomness and Combinatorial Constructions
  [Info] [Topics]
  This course will have two main, tightly woven, threads: the study of conditional results about pseudorandomness and derandomization, showing that if certain complexity-theoretic conjectures are true then every probabilistic algorithm has an efficient deterministic simulations; and the study of (unconditional) explicit construction of pseudorandom objects, such as randomness extractors and expander graphs.

  • Computational definition of pseudorandomness
  • Achieving pseudorandomness against simple adversaries: pairwise indepent generators; epsilon-biased generators; almost k-wise independent generators. Connection with error-correcting codes
  • Cryptographically strong pseudorandom generators: the Blum-Micali-Yao construction, the Goldreich-Levin theorem, the coding-theoretic and Fourier-analytic interpretations of the Goldreich-Levin theorem
  • Pseudorandom generators for derandomization: the Nisan-Wigderson generator and the Impagliazzo-Wigderson worst-case to average case reduction. Another coding-theoretic connection
  • Other conditional derandomization results: uniform setting, non-deterministic adversaries...
  • Randomness extractors from the Nisan-Wigderson generator and from other coding-theoretic constructions
  • Extractors, hash functions, Nisan's pseudorandom generator and Nisan-Zuckerman pseudorandom generator for space-bounded computation
  • Seedless extractors and applications of additive number theory
  • Composition of extractors, extractors for high min-entropy
  • Expander graphs, random walks, eigenvalues
  • Simple constructions of expander with super-constant degree
  • Construction of expanders using the Zig-Zag graph product
  • Reingold's theorem
  Date: Fall 2005
  Lecturer: Luca Trevisan
  Comment: Zero-knowledge are explained using explicit proofs for discrete-logarithm. It also covers NIZK, HVZK, ZAP.
  

• David Zuckerman
  CS 395T - Pseudorandomness and Combinatorial Constructions
  [Info] [Topics]
  Randomization is very useful in almost all areas of computer science, such as algorithms, cryptography, and distributed computing. These uses of randomness seem wonderful until one realizes that computers do not use truly random bits. Instead, most computers get their random bits by using pseudorandom generators. A pseudorandom generator is a deterministic algorithm that takes as input a short random seed and outputs a long string which is ``random'' enough for the purpose at hand.
  In this course, we will develop provably good pseudorandom generators for a variety of tasks. Along the way, we will frequently require explicit combinatorial constructions. That is, we will want to efficiently and deterministically construct a combinatorial object whose existence is easily ensured by the probabilistic method. In fact, a pseudorandom generator is such an object.
  
  Semester: Spring 2001
  Instructor:David Zuckerman
  Level: Graduate
  Comment: Proposed by Rong Ma .
  

Homepage