Wednesday, September 30, 2015

Lecture 19

Lautemann's proof that BPP is in Σp2∩Πp2.

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

Monday, September 28, 2015

Friday, September 25, 2015

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


Wednesday, September 23, 2015

Lecture 16

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

Monday, September 21, 2015

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.

Friday, September 18, 2015

Lecture 14

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

Arefin will finish that proof on Wednesday.

Wednesday, September 16, 2015

Monday, September 14, 2015

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

Friday, September 11, 2015

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 ACC0 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 AC1 which implies NL is in AC1.




Wednesday, September 9, 2015

Lecture 10

Circuit Classes in increasing power
NCi: Poly-size bounded-fan-in O(logi n) depth
ACi: Poly-size unbounded-fan-in O(logi n) depth
ACCi: ACi with mod k gates for some k
TCi: ACi with majority gates
TCi is contained in NCi+1

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

Friday, September 4, 2015

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. 

Wednesday, September 2, 2015

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