The Final Lecture.
NEXP not in ACC0, part II.
Scribe Notes by Tom Hayden
Wednesday, December 1, 2010
Monday, November 29, 2010
Lecture 29
Final Exam posted on assignments page.
NEXP not in ACC0
Scribe Notes by Manolis Pountourakis
Non-Uniform ACC Circuit Lower Bounds by Ryan Williams
NEXP not in ACC0
Scribe Notes by Manolis Pountourakis
Non-Uniform ACC Circuit Lower Bounds by Ryan Williams
Wednesday, November 24, 2010
Lecture 28
S2P
Scribe Notes by Michele Budinich
Scribe Notes by Michele Budinich
- Symmetric Alternation Captures BPP by Russell and Sundaram
- S2P in ZPPNP by Cai
- On the Complexity of Succinct Zero-Sum Games by Fortnow, Impagliazzo, Kabanets and Umans
Monday, November 22, 2010
Lecture 27
PCP Post Mortem
Scribe Notes by Tom Hayden
Approximation Classes, Parallel Repetition, Uniques Games, Max Cut
Scribe Notes by Tom Hayden
Approximation Classes, Parallel Repetition, Uniques Games, Max Cut
- Uniques Games Survey by Subhash Khot
- Semidefinite Programming for Max Cut by Goemans and Williamson
- Two-query PCP with subconstant error by Ran and Moshkovitz
Friday, November 19, 2010
Wednesday, November 17, 2010
Monday, November 15, 2010
Friday, November 12, 2010
Wednesday, November 10, 2010
Lecture 22
PCP Theorem Continued: Gap Amplification
Scribe Notes by Arefin Huq
Scribe Notes by Arefin Huq
- Expander Survey by Hoory, Linial and Wigderson.
Monday, November 8, 2010
Lecture 21
PCP Theorem: The Proof Begins
Scribe Notes by Arefin Huq
Scribe Notes by Arefin Huq
- On Dinur's proof of the PCP theorem by Radhakrishnan and Sudan
Breaking News: Ryan Williams proves NEXP not in ACC0
Friday, November 5, 2010
Lecture 20
The PCP Theorem Part I
Assignment 4 posted and due Wednesday, November 17.
Scribe Notes by Manolis Pountourakis.
Assignment 4 posted and due Wednesday, November 17.
Scribe Notes by Manolis Pountourakis.
- The PCP theorem by gap amplification by Irit Dinur
- Proof verification and the hardness of approximation problems by Arora, Lund, Motwani, Sudan and Szegedy (the original PCP theorem)
Wednesday, November 3, 2010
Monday, November 1, 2010
Friday, October 29, 2010
Wednesday, October 27, 2010
Monday, October 25, 2010
Friday, October 22, 2010
Wednesday, October 20, 2010
Monday, October 18, 2010
Lecture 12
Natural Proofs, BPP in P/poly
Scribe Notes by Manolis Pountourakis
Scribe Notes by Manolis Pountourakis
- Natural Proofs. Original paper by Razborov and Rudich
- Lance's Natural Proofs Blog Post
Friday, October 15, 2010
Wednesday, October 13, 2010
Monday, October 11, 2010
Lecture 9
Assignment 2 Posted and due Wednesday, October 20.
Topics: Time-space tradeoffs, introduction to probabilistic classes.
Scribe Notes by Darrell Hoy
Two proofs of Schwartz-Zippel
Topics: Time-space tradeoffs, introduction to probabilistic classes.
Scribe Notes by Darrell Hoy
Two proofs of Schwartz-Zippel
Friday, October 8, 2010
Wednesday, October 6, 2010
Monday, October 4, 2010
Lecture 6
Topic: Circuit Complexity
Scribe Notes by Nima Haghpanah
Papers:
Scribe Notes by Nima Haghpanah
Papers:
- Furst-Saxe-Sipser, Ajtai: Parity not in AC0
- Yao: Exponential lower bounds for Parity
- Hastad: Tight bounds for Parity
- Razborov-Smolensky: Lower bounds for Modp with Modq circuits
- Razborov: Monotone Lower Bounds for Clique
- Fortnow-Laplante: Razborov's proof of Hastad's result via Kolmogorov complexity
Friday, October 1, 2010
Lecture 5
Scribe Notes by David Barbella
Topics: Polynomial-Time Hierarchy, P/poly
Papers Mentioned:
Topics: Polynomial-Time Hierarchy, P/poly
Papers Mentioned:
- Karp-Lipton: PH collapses to second level if NP in P/poly
- Buhrman-Hitchcock: PH collapses to third level if there are subexponential-sized NP-complete sets
Wednesday, September 29, 2010
Monday, September 27, 2010
Lecture 3
Scribe Notes by Michele Budinich
Compendium of Complete Problems in Second Level and Higher (Schaefer and Umans)
Relevant Papers:
Compendium of Complete Problems in Second Level and Higher (Schaefer and Umans)
Relevant Papers:
- S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.
- M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.
Friday, September 24, 2010
Wednesday, September 22, 2010
Subscribe to:
Posts (Atom)