# Small circuits for circuit evaluation problem

Let $\mathsf{CircuitEval}_{s, n}$ be the function which maps an $s$-gate circuit $C$ on $n$ bits and an $n$-bit string $x$ to $C(x)$. Assume that circuits are encoded as an acyclic sequence of assignments $k := g(i, j)$ where $i, j, k$ are wire labels.

I know this is a bit of a funny question, but what is the best known upper bound on the circuit complexity of this problem? There is an $O((s + n)^2)$ single-tape TM computing this function, and so by the Fischer-Pippenger simulation, size $O((s + n)^2 \log(s + n))$ should suffice. The quadratic comes from having to seek back and forth. Is it possible to do better? Is it possible to do in size $O(s + n)$?

I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear time multitape TM and also that there are reductions from multitape TMs to circuits which give only a quasilinear size blowup. That is, Circuit Eval has circuits of size $(n+s)\log^{O(1)}(n+s)$, as per your formulation.