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 Σ^P₂∪Π^P₂.

Links:

• Fast Probabilistic Algorithms for Verification of Polynomial Identities by Jack Schwartz
• Probabilistic algorithms for sparse polynomials by Richard Zippel
• Two theorems on random polynomial time by Len Adleman. Shows that BPP is in P/poly.
• A complexity theoretic approach to randomness by Michael Sipser and BPP and the polynomial hierarchy by Clemens Lautemann. Show BPP in  Σ^P₂∪Π^P₂
• Wikipedia articles (with good definitions and proofs) for BPP, Schwartz-Zippel, Polynomial Identity-Testing and BPP in  Σ^P₂∪Π^P₂.