Friday, October 20, 2017

Day 24

Assignment 2 solutions have been posted on the T-Square resources page. A reminder that Assignment 3 is now available and is due November 1.

We gave the public-coin protocol for Graph Non-Isomorphism and showed that MA is contained in AM.

  • Public-coin protocol write up by Jonathan Katz

Wednesday, October 18, 2017

Day 23

Assignment 3 has been posted on T-Square and due November 1. Assignment 2 grades have been released. Solutions to assignment 2 will be posted in the T-Square resources shortly.

Started our unit on Arthur-Merlin games.

Defined AM and gave the private-coin protocol for graph non-isomorphism and informally described the public coin protocol. We'll do a detailed public-coin protocol on Friday.

Monday, October 16, 2017

Day 22

Today we did the Schwartz-Zippel lemma and used it to give a co-RP algorithm for polynomial identity-testing.

We also showed that BPP is in P/poly and in ΣP2∪ΠP2.

Links:

Friday, October 13, 2017

Day 21

We did the proof of the Chernoff Bounds. Here is a detailed write-up.

We also discussed the polynomial identity testing question: Given a polynomial p(x1,...,xn) described by a circuit of product and sum gates, is that polynomial exactly zero?

To give a probabilistic algorithm for polynomial identity testing we looked at the Schwartz-Zippel lemma and gave part of the proof.

Wednesday, October 11, 2017

Day 20

We introduced probabilistic Turing machines and talked about the classes BPP, RP and ZPP.

A language is in BPP if there is a probabilistic polynomial-time Turing machine such that for all x,

  • If x is in L then the probability that M(x) accepts is at least 2/3.
  • If x is not in L then the probability that M(x) accepts is at most 1/3.

A language is in RP if there is a probabilistic polynomial-time Turing machine such that for all x,

  • If x is in L then the probability that M(x) accepts is at least 1/2.
  • If x is not in L then the probability that M(x) accepts is 0.
A language is in ZPP if there is a probabilistic expected polynomial-time Turing machine such that for all x,

  • If x is in L then the probability that M(x) accepts is 1.
  • If x is not in L then the probability that M(x) accepts is 0.
We sketched why Composite testing is in RP and used Chernoff bounds to reduce the error in probabilistic algorithms to exponentially small. The exact statement of Chernoff bounds I gave in class was incorrect--we'll revisit on Friday.

Links:

Friday, October 6, 2017

Day 19

Finished proof of Razborov-Smolensky. Links in Day 18 post.

Kannan's non-constructive proof that Σp2 does not have nk-size circuit for any constant k.

Links:

Wednesday, October 4, 2017

Day 18

First half of Razborov-Smolensky proof that depth d circuits of Mod3, AND, OR and NOT gates computing parity must have an exponential number of gates.

Links:

Monday, October 2, 2017

Day 17

P-complete sets including Monotone Circuit Value: Given a circuit of just AND/OR gates with variables set to the constants TRUE and FALSE, will the circuit evaluate to TRUE?

The major results in circuit complexity:
  • Parity requires exponential-size circuits. 
  • For distinct primes p and q, there is no polynomial-size constant-depth circuit with AND, OR, NOT and Modp gates that can compute the Modq function.
  • Clique and Matching do not have polynomial-size monotone circuits even with arbitrary depth.
  • *NEXP does not have constant-depth circuits with Modm gates for any fixed m, prime or composite. 
Links: