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

U.S.A.

PHONE: (608) 262-3158

EMAIL: jyc AT cs DOT wisc DOT edu

Book/Lecture Notes

- An (incomplete) textbook
pdf

- A template for scribes
template.tex

- 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
three-bits.pdf

- multitape Turing machine simulated by a two tape Turing machine
two-tape-simulation-log-n-delay.pdf

- Non-deterministic Time Hierarchy Theorem (Cook)
Cook-Theorem.pdf

- Non-deterministic Time Hierarchy Theorem (Seiferas, Fischer, Meyer)
Seiferas-Fischer-Meyer.pdf

- Non-deterministic Time Hierarchy Theorem (Zak)
Zak.pdf

- Random Walk (Gobel-Jagers)
Gobel-Jagers.pdf

- Private Coin Versus Public Coin (Goldwasser-Sipser)
Goldwasser-Sipser.pdf

- Toda's Theorem (Toda)
Toda.pdf

- Connectivity in Logspace (Reingold)
Reingold.pdf

- Survey on PCP (RADHAKRISHNAN-SUDAN)
RADHAKRISHNAN-SUDAN.pdf

- S2 (JCSS journal version)
S2.pdf

- MIP=NEXP (Babai, Fortnow, Lund)
Babai-Fortnow-Lund.pdf

- 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.