Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
In here on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'.
Can we have randomized $2^{n^{o(1)}}poly(m)$ time in above statement?
Is there a similar result that would give $E\not\subseteq SIZE(2^{\delta n})$ (this would give $P=BPP$)?
How large can $o(1)$ be in the statement above and in 1. if applicable (can it be as large as $1/\log\log n$)?
The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the chapter on circuit complexity), and then you can show using this time $2^{n^{o(1)}}poly(m)$ Circuit SAT algorithm that $\Sigma_2^p\subseteq DTIME[2^{n^{o(1)}}]$, which contradicts the time hierarchy theorem (I can edit in a hint for this if this is desirable).
If we replaced the assumption, we would no longer get anything we know to be a contradiction in the above argument. As one of the comments mentioned, it is currently open whether $ZPP=EXP$, and even a substantially weaker version of the proposition with a randomized algorithm would give us this separation (note, as the comment says, $BPP$ and $ZPP$ are contained in $P/poly$).
It is known that if $P = NP$ (so in the flavor of the above, if Circuit SAT has a $poly(n+m)$ time algorithm), we get exponential size lower bounds against $E$. This follows as we know $E^{\Sigma_2^p}$ has exponential size lower bounds, and if $P=NP$, then $E=E^{\Sigma_2^p}$. I'm not sure who this argument first came from, but the idea is that using a $\Sigma_2^p$ oracle, on an input $x$ of length $n$, we can find the lexicographically first truth table of an $n$-bit boolean function with the maximum circuit complexity over $n$-bit boolean functions in time $2^{O(n)}$. After doing this, we can simply look up the value of $x$ in this truth table and output accordingly. In doing this, not only are we computing a function which requires exponential sized circuits, but we are actually showing, as Ricky pointed out in the comments, that $E^{\Sigma_2^p}$ has a language of maximum circuit complexity.
Also, to clarify a point mentioned in the post, to get $P=BPP$, you actually need that $E$ does not even infinitely often have circuits of size $2^{\delta n}$. This does follow from $P=NP$, but it is a stronger hypothesis than $E\not\subset SIZE[2^{\delta n}]$.
The argument above works for any runtime that falls into $2^{n^{o(1)}}$, so this includes $2^{n^{1/\log\log(n)}}$.
