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)



P/poly algorithm for polynomial identity testing
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>


