If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ To begin with PIT is in coRP, so at the very least you need something else to get you from RP to BPP. $\endgroup$– Emil JeřábekCommented Mar 18, 2018 at 8:31
-
$\begingroup$ Is $PIT \in P$ known now? There are two questions today which indicate there has been some progress. $\endgroup$– Samuel SchlesingerCommented Mar 18, 2018 at 17:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
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.
answered Mar 19, 2018 at 5:33
-
1$\begingroup$ The "exact $\to$ approximate" gap was closed by Impagliazzo and Wigderson. $\endgroup$ Commented Mar 19, 2018 at 8:15
-
-
1$\begingroup$ 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. $\endgroup$ Commented Mar 19, 2018 at 12:49
-
1$\begingroup$ Not that I know of. That’s my point: in order to actually derandomize PIT, we only know methods that require exponential circuit lower bounds, same as for BPP. $\endgroup$ Commented Mar 19, 2018 at 15:08
-
1$\begingroup$ I agree that your answer is correct for the question as stated, I was just worried that it was prone to misinterpretation. $\endgroup$ Commented Mar 19, 2018 at 17:26