Non-Uniform Lower Bounds for NSPACE

Question

If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$ where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of size $2^{O(n)}$ to an NP oracle, and ${\rm SIZE(n)}$ is the class of functions solvable by non-uniform circuits of size $O(n)$.

Since ${\rm NSPACE}[n]\subseteq E \subseteq E^{NP}$ the above observation implies that the question of whether ${\rm NSPACE}[n]\subseteq {\rm SIZE}[n]$ is open.

Questions:

1. What is the smallest function $f(n)$ such that it is known unconditionally that ${\rm NSPACE}[f(n)]\nsubseteq {\rm SIZE}[n]$?
2. What is the smallest class $\mathcal{C}$ containing $E^{NP}$ such that it is known unconditionally that $\mathcal{C}\nsubseteq SIZE[n]$?
3. What is a good reference for relations between uniform and non-uniform circuit classes?

Answer 1

1. For any space-constructible function $f$ such that $f(n)=\omega(n)$, we have $\mathrm{NSPACE}(f(n)\log n)\nsubseteq\mathrm{SIZE}(n)$. This follows by simple brute force: you can compute the predicate

$\exists$ a truth-table $t$ of a Boolean function in $O(\log f(n))$ variables such that ($\forall$ circuit $C$ of size $f(n)$, $C$ does not compute $t$) and ($\forall$ truth-tables $t'$ lexicographically smaller than $t$, $\exists$ a circuit of size $O(f(n))$ that computes $t'$) and $t(x)=1$

(where $x$ is the given input of length $n$) on an alternating TM with space $O(f(n)\log n)$ and $O(1)$ alternations, hence in $\mathrm{NSPACE}(O(f(n)\log n))$ by the Immerman–Szelepcsényi theorem. (The $\log n$ factor comes from the fact that a description of a circuit of size $f(n)$ takes $O(f(n)\log f(n))$ bits; we may assume $f(n)\le n^2$, thus $\log f(n)=O(\log n)$.)

2. The same kind of argument shows that $\mathrm{TIME}(n^{f(n)})^\mathrm{NP}\nsubseteq\mathrm{SIZE}(n)$ for any function $f(n)$ as above. However, this is really overkill. For example, it is known that oblivious $S_2^\mathrm P$ is also not contained in $\mathrm{SIZE}(n)$ (or $\mathrm{SIZE}(n^k)$ for any fixed $k$, for that matter), and it sits fairly low in the polynomial-time hierarchy, hence it is “almost” a much smaller class than $\mathrm{E^{NP}}$.