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
No comments:
Post a Comment