# Query on consequences of $\mathsf{P=BPP}$

We know $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$ or permanent does not have polynomial sized circuits. However permanent needs superpoly circuits imply $\mathsf{NEXP\not\subseteq P/Poly}$ since $\mathsf{P^{\#P}\subseteq PSPACE\subseteq NEXP}$. So why dont we just say $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$?

• Where have you seen "... or permanent does not have polynomial sized circuits"? (I've only seen "... or permanent does not have polynomial sized arithmetic circuits".) – user12859 Dec 30 '15 at 3:38
• @RickyDemer is it not true if permanent does not have poly size arith ckts then nexp is not in p/poly? – 1.. Dec 30 '15 at 3:47
• That implication is probably true, since its conclusion is probably true. – user12859 Dec 30 '15 at 4:33
• @RickyDemer ' probably true' is different from already known. is it not already known? – 1.. Dec 30 '15 at 4:37
• (Bear in mind that your earlier comment only asked about truth.) Yes, that's not already known. – user12859 Dec 30 '15 at 4:51

The conclusion is that the permanent does not have polynomial-size (constant-free) arithmetic circuits or $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$. Permanent not having polynomial-size constant-free arithmetic circuits is not known to imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$.
However, there are a couple more recent similar results whose conclusion is not a disjunction, but simply a lower bound on some polynomial family in $\mathsf{NEXP}$:
• Jansen and Santhanam showed that if PIT is in $\mathsf{NSUBEXP}$ then there is a family of polynomial whose integer evaluation problem is in $\mathsf{NEXP}$ but which do not have poly-size constant-free arithmetic circuits.
• Carmosino, Impagliazzo, Kabanets, and Kolokolova show that if PIT over a fixed finite field is in $\mathsf{NSUBEXP}$ then there is a multilinear polynomial whose evaluation problem over that same finite field is in $\mathsf{NE}$ that does not have poly-size arithmetic circuits. (This paper also has many other results of interest, including true hardness-to-randomness equivalences, avoiding many of the usual caveats.)
• @joshuagrchow does $\mathsf{NEXP}$ not having poly-size constant-free arithmetic circuits with some additional condition known to imply $\mathsf{NEXP}\not\subseteq\mathsf{P/poly}$? If so what is that additional condition? – 1.. Dec 31 '15 at 1:10