<p>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 (<a href="http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.645" rel="nofollow noreferrer">Carmosino-Impagliazzo-Kabanets-Kolokolova APPROX-RANDOM '15</a>). (And a similar result holds over $\mathbb{Z}$.) This is an <em>algebraic</em> circuit lower bound on $\mathsf{NE} \subseteq \mathsf{NEXP}$. </p>

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

<p>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}$.</p>

<p>(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...")</p>

<p>*Over a fixed finite field this is probably the easiest one to overcome.</p>

CC BY-SA 3.0
2018-03-19T08:15:36.093Z
The "exact $\to$ approximate" gap was closed by Impagliazzo and Wigderson.
Emil Jeřábek
CC BY-SA 3.0
2018-03-19T10:24:53.583Z
@EmilJeřábek which paper?
Turbo
CC BY-SA 3.0
2018-03-19T11:00:11.793Z
The famous one: "P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma".
Emil Jeřábek
CC BY-SA 3.0
2018-03-19T12:49:23.027Z
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.
Emil Jeřábek
CC BY-SA 3.0
2018-03-19T13:54:05.893Z
@EmilJeřábek: About IW, of course, at some point I knew that :P. For PIT, Kabanets-Impagliazzo only gets you *quasi*-poly time from an exponential algebraic circuit lower bound. Has this been extended to get PIT in P from some lower bound assumption (weaker than that needed to get P=BPP)?
Joshua Grochow
CC BY-SA 3.0
2018-03-19T15:08:31.933Z
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.
Emil Jeřábek
CC BY-SA 3.0
2018-03-19T15:37:52.253Z
@EmilJeřábek: We agree on the facts, but I guess are just discussing the interpretation. (1) I though the OQ was about "Suppose someone manages to prove PIT in P by an arbitrary miracle. Then how far do we still have to go?" As in, "given what is *implied by* PIT in P, how much more is needed to prove P=BPP?" (2) I think there is a significant difference between exponential algebraic circuit lower bounds and exponential Boolean circuit lower bounds.
Joshua Grochow
CC BY-SA 3.0
2018-03-19T17:26:57.510Z
I agree that your answer is correct for the question as stated, I was just worried that it was prone to misinterpretation.
Emil Jeřábek
CC BY-SA 3.0
2018-03-19T18:11:02.227Z
Fair enough...I agree
Joshua Grochow
CC BY-SA 3.0
2018-03-19T05:33:09.440Z
2018-03-19T13:52:39.623Z
2018-03-19T13:52:39.623Z
Joshua Grochow
<p>If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?</p>

CC BY-SA 3.0
2018-03-18T08:31:48.843Z
To begin with PIT is in coRP, so at the very least you need something else to get you from RP to BPP.
Emil Jeřábek
CC BY-SA 3.0
2018-03-18T17:08:07.883Z
Is $PIT \in P$ known now? There are two questions today which indicate there has been some progress.
Samuel Schlesinger
<big-picture><derandomization>
From $PIT\in P$ to $P=BPP$
Turbo
# From $PIT\in P$ to $P=BPP$

(Asked by: username_0 on 2018-03-18)

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

**Tags:** big-picture, derandomization

> **Comments:**
> **username_1**: To begin with PIT is in coRP, so at the very least you need something else to get you from RP to BPP.  
> **username_2**: Is $PIT \in P$ known now? There are two questions today which indicate there has been some progress.  

---

## 1 answers

### Answer by username_3 on 2018-03-19. Score: 3 | Accepted answer

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](http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.645)). (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.

> **Comments:**
> **username_1**: The "exact $\to$ approximate" gap was closed by Impagliazzo and Wigderson.  
> **username_0**: @EmilJeřábek which paper?  
> **username_1**: The famous one: "P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma".  
> **username_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.  
> **username_3**: @EmilJeřábek: About IW, of course, at some point I knew that :P. For PIT, Kabanets-Impagliazzo only gets you *quasi*-poly time from an exponential algebraic circuit lower bound. Has this been extended to get PIT in P from some lower bound assumption (weaker than that needed to get P=BPP)?  
> **username_1**: 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.  
> **username_3**: @EmilJeřábek: We agree on the facts, but I guess are just discussing the interpretation. (1) I though the OQ was about "Suppose someone manages to prove PIT in P by an arbitrary miracle. Then how far do we still have to go?" As in, "given what is *implied by* PIT in P, how much more is needed to prove P=BPP?" (2) I think there is a significant difference between exponential algebraic circuit lower bounds and exponential Boolean circuit lower bounds.  
> **username_1**: I agree that your answer is correct for the question as stated, I was just worried that it was prone to misinterpretation.  
> **username_3**: Fair enough...I agree  

---

