CS 710: Computational Complexity
Time: 11:00 AM -- 12:15 PM T Th.
Room: CS 1207,
Office hours: Tuesdays and Thursdays 1:00 PM -- 2:15 PM.
Professor: Jin-Yi Cai
Computer Sciences Department
Office Room CS 4393
University of Wisconsin - Madison
1210 West Dayton Street
Madison, WI 53706
PHONE: (608) 262-3158
EMAIL: jyc AT cs DOT wisc DOT edu
- An (incomplete) textbook
- A template for scribes
- Smolensky's paper pdf of the paper
- Constant Width Branching programs Barrington's paper
- Subquadratic Simulations Subquadratic.pdf
- Three bits bottleneck: Turing machines that almost violate space hierarchy
- multitape Turing machine simulated by a two tape Turing machine
- Non-deterministic Time Hierarchy Theorem (Cook)
- Non-deterministic Time Hierarchy Theorem (Seiferas, Fischer, Meyer)
- Non-deterministic Time Hierarchy Theorem (Zak)
- Random Walk (Gobel-Jagers)
- Private Coin Versus Public Coin (Goldwasser-Sipser)
- Toda's Theorem (Toda)
- Connectivity in Logspace (Reingold)
- Survey on PCP (RADHAKRISHNAN-SUDAN)
- S2 (JCSS journal version)
- MIP=NEXP (Babai, Fortnow, Lund)
- week of Jan 17, 2017: Constant Depth Circuits, Razborov-Smolensky Proof.
- week of Jan 24, 2017: TM, 1-tape vs. 2-tape vs. k-tape. TlogT simulation. branching programs.
- week of Jan 31, 2017: constant slow-down in NTM simulation. hierarchy thms. Savitch, Immerman-Szelepcsenyi Theorem.
- week of Feb 7, 2017: Random walks. Undirected st-connectivity. st-commute.
- week of Feb 14, 2017: Alternation, Oracle TM, relativization. P-time hierarchy
- week of Feb 21, 2017: P/poly, Karp-Lipton theorem, Mahaney theorem (with a proof by Ogihara and Watanabe).
- week of Feb 28, 2017: BPP, Sipser-Lautemann, fat-thin sets, universal hashing. MaxCut and Goemans-Williamson.
- week of March 7, 2017: Isolation lemma, approximate counting, unique SAT. ZPP, RP. S2.
- week of March 14, 2017: S2 in ZPP^NP.
- March 18-26 Spring break.
- week of March 28, 2017: IP, AM, public versus private coins. GNI.
- week of April 4, 2017: LFKN protocol. List decoding. Average case complexity of permanent.
- week of April 11, 2017: IP = PSPACE. Communitative diagrams. PP closure.
- week of April 18, 2017: Newman's rational approximation, truth-table reduction, Toda's theorem.