- big-picture derandomization
- Updated Sat, 04 Jun 2022 22:56:04 GMT

If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?

If PIT over a finite field $F$ is in P, then there is a family of multilinear polynomials whose graph is decidable in $\mathsf{NE}$ but which does not have poly-size $F$-algebraic circuits (Carmosino-Impagliazzo-Kabanets-Kolokolova APPROX-RANDOM '15). (And a similar result holds over $\mathbb{Z}$.) This is an *algebraic* circuit lower bound on $\mathsf{NE} \subseteq \mathsf{NEXP}$.

To get $\mathsf{P} = \mathsf{BPP}$ out of, e.g., Nisan-Wigderson (& Impagliazzo-Wigderson), one needs a *Boolean* (sub)exponential circuit lower bound on functions in (deterministic) $\mathsf{EXP}$.

So, on the one hand, an algebraic circuit lower bound on $\mathsf{NEXP}$ is a lot closer to $\mathsf{P} = \mathsf{BPP}$ than we are today, but still seems pretty far in some absolute sense: algebraic -> Boolean*, super-poly lower bound -> exponential, and $\mathsf{NEXP}$ -> $\mathsf{EXP}$.

(Of course, as discussed by Emil Jerabek in the comments, if one uses Impagliazzo-Kabanets to get PIT in $\mathsf{quasiP}$ by giving an exponential algebraic circuit lower bound, then the "super-poly -> exponential" gap goes away. But I took the question to mean "Suppose $PIT \in \mathsf{P}$ by any arbitrary method...")

*Over a fixed finite field this is probably the easiest one to overcome.

- +1 – The "exact $\to$ approximate" gap was closed by Impagliazzo and Wigderson. — Mar 19, 2018 at 08:15
- +0 – @EmilJeábek which paper? — Mar 19, 2018 at 10:24
- +1 – By the way, I think it might be a bit misleading to suggest that derandomization of PIT corresponds to superpolynomial lower bounds, and derandomization of BPP to exponential lower bounds. In fact, for PIT and BPP alike, the only bounds we know to imply full derandomization are exponential, and the only bounds known to follow from derandomization are superpolynomial. So, this reflects a gap in our understanding of the situation rather than any difference between PIT and BPP. — Mar 19, 2018 at 12:49
- +1 – Not that I know of. Thats my point: in order to actually derandomize PIT, we only know methods that require exponential circuit lower bounds, same as for BPP. — Mar 19, 2018 at 15:08
- +1 – I agree that your answer is correct for the question as stated, I was just worried that it was prone to misinterpretation. — Mar 19, 2018 at 17:26

External links referenced by this document: