User:Srikanth srinivasan/Sandbox

An article on Polynomial Identity Testing

Related article on PIT

Things I wish to write about:

1. The importance of PIT in complexity theory
   1. The connection to circuit lower bounds via KI.
2. Derandomizing identity tests
   1. The old Chen-Kao and Lewin-Vadhan results.
   2. The Klivans-Spielman result, and the new program.
   3. The Dvir-Shpilka result, and the rank conjecture.
   4. The Kayal-Saraf result.
3. Derandomizing Schwarz Zippel using an NW generator construction.
4. Manindra's ideas.

The importance of Polynomial Identity Testing in Complexity Theory

In the absence of complete problems for the complexity class BPP, attempts at derandomizing the complexity class BPP have taken two routes:

1. Trying to prove a general result that generally does something stronger: for example, also works for promise-BPP.
2. Trying to come up with deterministic algorithms for specific problems known to have randomized algorithms.

Results of the first kind have been conditional, whereas the latter approach, though not likely to show that P=BPP, have yielded several deterministic polynomial time algorithms for problems that were previously known to have randomized polynomial time algorithms only.