Lecture 19

Lautemann's proof that BPP is in Σ^p₂∩Π^p₂.

Informal notion of Merlin-Arthur games and example of proof of graph non-isomorphism.

Lecture 18

Arefin finished the switching lemma.

Lecture 17

Assignment 2 posted on T-Square due October 5 at 5 PM

Probabilistic Complexity Classes: PP, BPP, RP and ZPP.
Can assume error is 1-2^{q(n)} for any polynomial q
Showed NP in PP, RP in BPP in P/poly
HW to show ZPP = RP ∩ co-RP

Lecture 16

Arefin finished Barrington's Theorem and started Håstad switching lemma.

Lecture 15

Randomized Algorithms introduced with primality testing based on Fermat's Little Theorem. Fails to work on Carmichael Numbers so need a different test: Miller-Rabin. Primality was shown to have a deterministic polynomial-time solution  in Agrawal-Kayal-Saxena.

Homework assignment two will be distributed on Friday.

Lecture 14

Conclusion of Razborov-Smolenksy and start of Barrington's Theorem that NC¹ has poly-size bounded-width branching programs. Proofs in Boppana-Sipser.

Arefin will finish that proof on Wednesday.

Lecture 13

Razborov-Smolensky continued.

Lecture 12

Razborov-Smolensky proof that Parity cannot be computed by poly-size constant depth circuits with Mod-3 gates.

Section 3.8 of Boppana-Sipser

Lecture 11

Assignment 1 is returned via T-Square. Above a 50 is a reasonable grade. We discussed the solution to showing that 3:a->b which you can find as Theorem 2 here.

We discussed many circuit results, the ones before 1989 with proofs are summarized nicely in
The Complexity of Finite Functions by Boppana and Sipser

Two more recent results:
NEXP not in ACC⁰ by Ryan Williams
PH infinite relative to a random oracle  by Benjamin Rossman, Rocco Servedio and Li-Yang Tan

We also showed matrix multiplication is in AC¹ which implies NL is in AC¹.

Lecture 10

Circuit Classes in increasing power
NCⁱ: Poly-size bounded-fan-in O(logⁱ n) depth
ACⁱ: Poly-size unbounded-fan-in O(logⁱ n) depth
ACCⁱ: ACⁱ with mod k gates for some k
TCⁱ: ACⁱ with majority gates
TCⁱ is contained in NCⁱ⁺¹

For more about these or any classes, see the Complexity Zoo.

Lecture 9

By popular demand, Assignment 1 deadline has been extended to Tuesday 9 AM. Extra credit to those who turn it in by the original deadline of 5 PM today.

Defined P/poly and showed the equivalence to languages accepted by poly-size circuits. Karp-Lipton Theorem showing that if NP is in P/poly then the polynomial time hierarchy collapses to the second level. 

Lecture 8

Circuit Complexity - P-completeness of circuit value. Polynomial-size circuit families

Completeness in the Polynomial-Time Hierarchy: A Compendium by Marcus Schaefer and Chris Umans