Polynomial Identity Testing
Here is an handout for the talk I gave in the Theory Student Seminar: Depth and rank considerations in the Polynomial Identity Problem.
I try to keep on this page a list of papers and surveys on the Polynomial Identity Testing problem. I do not know all the papers on this topic, so you can help me by sending me an email with references: ens-lyon.fr@Bruno.Grenet (reverse order).
For each paper, I give a link to an online PDF version of the paper. If possible, I give a link to ECCC or the ArXiV. Else I try to find the paper on one of the authors' webpage. If none of the previous solutions is possible, I nevertheless give a link where the paper is freely available.
Please let me know about any broken link.
Surveys
- N. Saxena. Progress on Polynomial Identity Testing. Bull. EATCS, 99:49-79, 2009. [ bib | pdf ]
- M. Agrawal and R. Saptharishi. Classifying Polynomials and Identity Testing. 2009. [ bib | pdf ]
- M. Agrawal. Proving Lower Bounds Via Pseudo-random Generators. In Proc. FSTTCS'05, page 92. Springer-Verlag New York Inc, 2005. [ bib | pdf ]
Deterministic PIT
Depth three
- N. Kayal and S. Saraf. Blackbox polynomial identity testing for depth 3 circuits. In Proc. FOCS'09, 2009. [ bib | pdf ]
- Z.S. Karnin and A. Shpilka. Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. In Proc CCC'08, pages 280-291, 2008. [ bib | pdf ]
- Z. Dvir and A. Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In Proc. STOC'05, pages 592-601. ACM New York, NY, USA, 2005. [ bib | pdf ]
- N. Saxena and C. Seshadhri. An Almost Optimal Rank Bound for Depth-3 Identities. In Proc. CCC'09, pages 137-148. IEEE Computer Society, 2009. [ bib | pdf ]
- N. Kayal and S. Saxena. Polynomial Identity Testing for Depth 3 Circuits. In Proc CCC'06, pages 9-17, 2006. [ bib | pdf ]
Depth four
- Zohar S. Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in, 2009. [ bib | pdf ]
- N. Saxena. Diagonal Circuit Identity Testing and Lower Bounds. In Proc. ICALP'08, page 71. Springer-Verlag, 2008. [ bib | pdf ]
Probabilistic PIT
- R.A. DeMillo and R.J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7(4):193-195, 1978. [ bib | pdf ]
- J.T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):717, 1980. [ bib | pdf ]
- R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM, volume 79, pages 216-226. Springer, 1979. [ bib | pdf ]
- Richard J. Lipton. The Curious History of the Schwartz-Zippel Lemma, 2009. [ bib | pdf ]
- Z.Z. Chen and M.Y. Kao. Reducing Randomness Via Irrational Numbers. SIAM J. Comput., 29(4):1247-1256, 2000. [ bib | pdf ]
- M. Agrawal and S. Biswas. Primality and identity testing via Chinese remaindering. In Proc. FOCS'99, pages 202-208, 1999. [ bib | pdf ]
- A.R. Klivans and D. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proc. STOC'01, pages 216-223. ACM New York, NY, USA, 2001. [ bib | pdf ]
Misc.
- M. Bläser, M. Hardt, R.J. Lipton, and N.K. Vishnoi. Deterministically testing sparse polynomial identities of unbounded degree. Information Processing Letters, 109(3):187-192, 2009. [ bib | pdf ]
- M. Agrawal and V. Vinay. Arithmetic Circuits: A Chasm at Depth Four. In Proc. FOCS'08, pages 67-75, 2008. [ bib | pdf ]
- E. Allender, J. Jiao, M. Mahajan, and V. Vinay. Non-commutative arithmetic circuits: depth reduction and size lower bounds. Theoretical Computer Science, 209(1-2):47-86, 1998. [ bib | pdf ]
- V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. In Proc. FOCS'03, pages 355-364, 2003. [ bib | pdf ]
This file was generated by bibtex2html 1.94.
Last modified: Jul 17, 2010