Timeline for From $PIT\in P$ to $P=BPP$
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2018 at 18:11 | comment | added | Joshua Grochow | Fair enough...I agree | |
| Mar 19, 2018 at 17:26 | comment | added | Emil Jeřábek | 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 15:37 | comment | added | Joshua Grochow | @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. | |
| Mar 19, 2018 at 15:08 | comment | added | Emil Jeřábek | 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. | |
| Mar 19, 2018 at 13:54 | comment | added | Joshua Grochow | @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)? | |
| Mar 19, 2018 at 13:52 | history | edited | Joshua Grochow | CC BY-SA 3.0 |
added 313 characters in body
|
| Mar 19, 2018 at 12:49 | comment | added | Emil Jeřábek | 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 11:00 | comment | added | Emil Jeřábek | The famous one: "P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma". | |
| Mar 19, 2018 at 10:24 | comment | added | Turbo | @EmilJeřábek which paper? | |
| Mar 19, 2018 at 10:24 | vote | accept | Turbo | ||
| Mar 19, 2018 at 8:15 | comment | added | Emil Jeřábek | The "exact $\to$ approximate" gap was closed by Impagliazzo and Wigderson. | |
| Mar 19, 2018 at 5:33 | history | answered | Joshua Grochow | CC BY-SA 3.0 |