# Derandomization of Polynomial Identity Testing

There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential circuits for infinitely many input lengths.

Hence there is a polynomial time deterministic algorithm thet solves the Polynomial Identity Testing problem, that works correctly if this condition ($DTIME (2^{O(n)})$ does not have sub-exponential circuits) is satisfied.

Can one state this algorithm explicitly?

• Please edit the title to be more related to your question (like "Derandomization of Polynomial Identity Testing") – Diego de Estrada Apr 7 '16 at 18:53
• The Impagliazzo–Wigderson theorem is that P=BPP unless each problem in E has subexponential circuits for infinitely many input lengths, not everywhere. – Emil Jeřábek Apr 7 '16 at 19:03
• Anyway, it’s not clear to me what the question is after. The proof of the theorem is perfectly constructive, so it gives an explicit algorithm: viz. the usual Ibarra–Moran PIT algorithm based on the Schwartz–Zippel–DeMillo–Lipton lemma, with pseudorandom bits supplied by the Nisan–Wigderson generator, whose “hard function” will be an error-corrected version of a language from E that requires exponential circuits. Do you want something else? – Emil Jeřábek Apr 7 '16 at 19:12