Skip Navigation

CSCE 424/824 - Computational Complexity Theory

CSCE 424/824: Computational Complexity Theory

Spring 2012

Room: CBA 306 Instructors: Derrick Stolee Steve Goddard
Time: TR 9:30--10:45am Office: Avery 336 Avery 267
Office Hours: MW 2:00--3:30pm Email: s-dstolee1@math.unl.edu goddard@cse.unl.edu
Textbook: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak

Syllabus

Course Goals

We will discuss the fundamentals of computational complexity theory as well as investigate some of the recent results on the edges of current research. The course shall begin by discussing the {\it core topics} of complexity theory. From this base of fundamental knowledge, we shall venture into {\it special topics} based on student preference. The topics are listed below.

Core Topics: These topics will be discussed in sequential order.

  • Chapter 1: The computational model.
  • Chapter 2: NP and NP-completeness.
  • Chapter 3: Diagonalization.
  • Chapter 4: Space complexity.
  • Chapter 5: The polynomial hierarchy and alternations.
  • Chapter 6: Boolean circuits.
  • Chapter 7: Randomized computation.

Special Topics: These topics will be discussed in order of student preference.

  • Chapter 8: Interactive proofs.
  • Chapter 11: PCP theorem and hardness of approximation.
  • Chapter 12: Decision trees.
  • Chapter 13: Communication Complexity.
  • Chapter 14: Circuit lower bounds.
  • Chapter 17: Complexity of counting.
  • Chapter 19: Hardness amplification and error-correcting codes.
  • Chapter 20: Derandomization.
  • Chapter 21: Pseudorandom constructions: Expanders and extractors.
  • Research: Reachability Problems in Space-Bounded Complexity.

Students are expected to meet with the instructor BY MARCH 14th to discuss preferences for the special topics. These meetings will be requested near the end of the discussions of core topics.

Problem Sets

>
Problem Set 1 Due 01/26 PDF TeX
Problem Set 2 Due 02/09 PDF TeX
Problem Set 3 Due 02/23 PDF TeX
Problem Set 4 Due 03/08 PDF TeX
Problem Set 5 Due 03/29 PDF TeX
Problem Set 6 Due 04/10 PDF TeX
Problem Set 7 Due 04/19 PDF TeX

Topics Covered

  1. 01/10: Definition of Turing Machines, Robustness.
  2. 01/12: Robustness, Computability, Halting Problem, Definition of P.
  3. 01/17: Polynomial-time Algorithms, Definition of NP, EXP, non-deterministic TMs.
  4. 01/24: Non-deterministic TMs, Reductions, NP-completeness, TMSAT.
  5. 01/26: Boolean functions, Cook-Levin Theorem.
  6. 01/31: IndSet is NP-complete, Existence vs. Search, coNP, NEXP.
  7. 02/02: Time Hierarchy Theorem, Nondeterministic Time Hierarchy Theorem, Statement of Ladner's Theorem.
  8. 02/07: Ladner's Theorem, Oracle Machines, Introduction to Space Complexity, Configuration Graphs.
  9. 02/09: Space-complexity graphs. Reachability.
  10. 02/14: Savitch's Theorem, Immerman-Szelepcseny Theorem, True Quantified Boolean Formulas.
  11. 02/16: TQBF is PSPACE-complete, Polynomial Hierarchy.
  12. 02/21: Alternating Turing Machines, Started Time-Space lower bounds for SAT.
  13. 02/23: Finished Time-Space lower bounds for SAT. PH and Oracles. Started Boolean Circuits.
  14. 02/28: P in P/poly, uniform circuits, TMs with advice.
  15. 03/01: P/poly as TM with advice, Karp-Lipton Theorem, Meyer's Theorem, Shannon's circuit bound.
  16. 03/06: NC, AC, Probabilistic Computation, BPP.
  17. 03/08: RP, coRP, ZPP, Robustness of probabilistic model.
  18. 03/13: Robustness, BPP in P/poly, BPP in Σ2.
  19. 03/15: Counting Complexity. Definition of FP, #P, PP.
  20. 03/27: Permanent, Perfect Matchings, Valiant's Theorem.
  21. 03/29: Remaining Counting Complexity Theorems, Toda's Theorem (no proof), Decision Trees.<
  22. 04/03: Decision trees, Certificate complexity.
  23. 04/05: Sensitivity, Block Sensitivity, Relationships between s, bs, C, and D. Evasiveness Conjecture.
  24. 04/10: Chapter 13: Communication Complexity
  25. 04/12: Chapter 13: Communication Complexity
  26. 04/17: Chapter 8: Interactive Proofs
  27. 04/19: Special Topic: Planar Reachability in UL
  28. 04/24: Special Topic: ReachFewL = ReachUL
  29. 04/26: Special Topic: Reachability in Surface-Embedded DAGs

Additional Resources