5
$\begingroup$

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

$\endgroup$
  • $\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řábek Mar 18 '18 at 8:31
  • $\begingroup$ Is $PIT \in P$ known now? There are two questions today which indicate there has been some progress. $\endgroup$ – Samuel Schlesinger Mar 18 '18 at 17:08
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The "exact $\to$ approximate" gap was closed by Impagliazzo and Wigderson. $\endgroup$ – Emil Jeřábek Mar 19 '18 at 8:15
  • $\begingroup$ @EmilJeřábek which paper? $\endgroup$ – T.... Mar 19 '18 at 10:24
  • 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$ – Emil Jeřábek Mar 19 '18 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$ – Emil Jeřábek Mar 19 '18 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$ – Emil Jeřábek Mar 19 '18 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.