P/poly algorithm for polynomial identity testing

2010-08-12T00:37:21Z

By the Schwartz–Zippel lemma, "Is this arithmetic formula identically zero?" is in coRP $\subseteq$ BPP $\subset$ P/poly, with the second inclusion by Adleman's theorem. By basically following the proof, but using the improved error bound that comes from the original algorithm only having one-sided error, one gets an algorithm that computes suitable advice. (equivalently, a suitable circuit)

Is there any known P/poly algorithm for this problem with advice that can be computed faster?

(I already know about www.cs.sfu.ca/~kabanets/Research/poly.html)

Answer by Ryan Williams for P/poly algorithm for polynomial identity testing

2010-08-12T08:13:45Z

The Schwartz-Zippel lemma is very fast, only one evaluation of the formula at one random point. There's nothing better known that minimizes time and error as well as Schwartz-Zippel. But Schwartz-Zippel requires a lot of randomness in each repetition: a fresh new point of n elements.

Have you tried some of the polynomial identity tests with better tradeoffs between randomness and error? Their running time (and the running time dependence on the error) is a bit worse than Schwartz-Zippel, but the number of random bits needed is much less than Schwartz-Zippel. So in the application of Adleman's theorem, the sizes of the witnesses you need to hard-code in the non-uniform circuit will shrink, but the time dependence on error increases, potentially making the number of necessary witnesses increase. Given these complex tradeoffs, I'm not sure which of them would work best for obtaining small circuits.

For a quick overview of these alternative identity tests and their tradeoffs, see the table on p.3 in Agrawal and Biswas: http://www.cse.iitk.ac.in/users/manindra/algebra/identity.pdf

P/poly algorithm for polynomial identity testing - MathOverflow

P/poly algorithm for polynomial identity testing

Answer by Ryan Williams for P/poly algorithm for polynomial identity testing