8
$\begingroup$

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)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Another way to reduce error with few random bits is to use any deterministic construction of expander graphs. $\endgroup$
    – Tsuyoshi Ito
    Aug 12, 2010 at 15:29
  • 2
    $\begingroup$ Yes, thanks! However that may be overkill here, as that works in a black-box way for any randomized algorithm. Polynomial identity testing has very special structure which the above algorithms exploit. $\endgroup$
    – Ryan Williams
    Aug 13, 2010 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.