This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.
1. We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let Missing-String be the (total) search problem of producing a string that does not appear in a given list $L$ containing $M$ bit-strings of length $N$, where $M < 2^n$. We show in a generic way how algorithms and uniform circuits (from restricted classes) for Missing-String imply complexity lower bounds (and in some cases, the converse holds as well).
a. We give a local algorithm for Missing-String, which can compute any desired output bit making very few probes into the input, when the number of strings $M$ is small enough. We apply this to prove a new nearly-optimal (up to oracles) time hierarchy theorem with advice.
b. We show that the problem of constructing restricted uniform circuits for Missing-String is essentially equivalent to constructing functions without small non-uniform circuits, in a relativizing way. For example, we prove that small uniform depth-3 circuits for Missing-String would imply exponential circuit lower bounds for $\Sigma_2 \text{EXP}$, and depth-3 lower bounds for Missing-String would imply non-trivial circuits (relative to an oracle) for $\Sigma_2 \text{EXP}$ problems. Both conclusions are longstanding open problems in circuit complexity.
2. We construct an oracle relative to which SAT can be solved in "half-exponential" time, yet exponential time ($\text{EXP}$) has polynomial-size circuits. Improving $\text{EXP}$ to $\text{NEXP}$ would give an oracle relative to which $\Sigma_2 \text{EXP}$ has "half-exponential" size circuits, which is open. (Recall it is known that $\Sigma_2 \text{EXP}$ is not in "sub-half-exponential" size, and the proof relativizes.) Moreover, the running time of the SAT algorithm cannot be improved: relative to all oracles, if SAT is in "sub-half-exponential" time then $\text{EXP}$ does not have polynomial-size circuits.
The conference version of this paper had an incorrect theorem (Theorem 1.10), pointed out to us by Jiatu Li. We have attached an erratum (coauthored with Jiatu Li) to the end of this paper, which includes a proof of the negation of Theorem 1.10.
