Wednesday, December 1, 2010

Lecture 30

The Final Lecture.

NEXP not in ACC0, part II.

Scribe Notes by Tom Hayden

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

Wednesday, November 24, 2010

Lecture 28

S2P

Scribe Notes by Michele Budinich

Monday, November 22, 2010

Lecture 27

PCP Post Mortem

Scribe Notes by  Tom Hayden

Approximation Classes, Parallel Repetition, Uniques Games, Max Cut


Friday, November 19, 2010

Lecture 26

Linearity Testing to end the PCP proof.

Wednesday, November 17, 2010

Lecture 25

PCP - Alphabet Reduction Part I

Scribe Notes by Darrell Hoy

Monday, November 15, 2010

Lecture 24

PCP Gap Amplification Continued

Friday, November 12, 2010

Lecture 23

PCP Continued. Transformation to reduce degree and turn graph into an expander.

Wednesday, November 10, 2010

Lecture 22

PCP Theorem Continued: Gap Amplification

Scribe Notes by Arefin Huq

Monday, November 8, 2010

Lecture 21

PCP Theorem: The Proof Begins

Scribe Notes by Arefin Huq

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.

Wednesday, November 3, 2010

Lecture 19

IP = PSPACE

Scribe Notes by Darrell Hoy

JACM Issue with all three IP=PSPACE papers

Monday, November 1, 2010

Friday, October 29, 2010

Lecture 17

Valiant-Vazirani

Scribe Notes by Greg Stoddard

Wednesday, October 27, 2010

Lecture 16

Counting Complexity

Scribe Notes by Adam Kalinich

Monday, October 25, 2010

Lecture 15

Barrington's Theorem

Lecture and Scribe Notes by Arefin Huq

Friday, October 22, 2010

Lecture 14

Assignment 3 due Wednesday, November 3.

Topic: Arthur-Merlin Games.

Scribe Notes by David Barbella

Wednesday, October 20, 2010

Lecture 13

The Complexity of BPP

Scribe Notes by Michele Budinich

Monday, October 18, 2010

Lecture 12

Natural Proofs, BPP in P/poly

Scribe Notes by  Manolis Pountourakis

Friday, October 15, 2010

Lecture 11

Razborov-Smolensky Part 2

Lecture by Arefin Huq

See notes from Lecture 10.

Wednesday, October 13, 2010

Lecture 10

Razborov-Smolensky Part I

Lecture and Scribe Notes by Arefin Huq

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

Friday, October 8, 2010

Lecture 8

Topics: Circuits between AC0 and NC1, lower bound theorems.
Scribe notes by Tom Hayden

Wednesday, October 6, 2010

Lecture 7

Topics: The world between NC1 and AC1, PRAMs

Scribe Notes by Adam Kalinich

Monday, October 4, 2010

Lecture 6

Topic: Circuit Complexity

Scribe Notes by Nima Haghpanah

Papers:

Friday, October 1, 2010

Lecture 5

Scribe Notes by David Barbella

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

Lecture 4

Assignment 1 posted on Assignments page, due Friday, October 8.

Scribe Notes by Greg Stoddard.

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:

  1. S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and HartmanisJournal of Computer and System Sciences 25:130-143. 1982.
  2. M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse setsSIAM Journal on Computing volume 20, pp.471–483. 1991.

Friday, September 24, 2010

Wednesday, September 22, 2010

Lecture 1

The P versus NP Problem.
Scribe Notes by Nicolas Renold