# Depth of circuit computing f(x) = "first n bit string with circuit complexity sqrt(n)"

I want to construct a depth $$\mathrm{poly}(n)$$ circuit computing $$f(x) = \text{first }n\text{ bit string with circuit complexity }\sqrt n$$ where $$x \in \{0, 1\}^n$$. I see how to do it with depth $$2^n$$ (have a level enumerating circuits of size at most $$\sqrt n$$ and OR their truth tables; then you can use AND gates to find the first OR that is a 0) but I can't get down to $$\mathrm{poly}(n)$$. Anyone see how?

• Can you edit your question to include what definition you are using of what it means for a string $s$ to have circuit complexity $c$?
– D.W.
Commented Sep 4 at 21:16
• I think this might be trivial. The way you phrased your question, the answer only depends on the length of the input. In a non-uniform model, you only need circuits of depth 1: for each input size $n$, the circuit $C_n$ can ignore the input and hard-codes the output. Commented Sep 5 at 3:46
• It seems to me you are confusing size and depth. I can't fully follow you description, but any sensible way of computing in parallel the truth tables of all circuits of size $\sqrt n$ in $\log n$ variables and then the lexicographically smallest among the results will have size $n^{O(\sqrt n)}$, but depth only $n^{O(1)}$. E.g., compute the $n$ output bits one by one. In fact, you can make it depth $O(\sqrt n(\log n)^2)$ or so: the smaller of two strings can be computed by a circuit of depth $O(\log n)$; arrange these into a balanced binary tree. I'm assuming fan-in 2 circuits, otherwise ... Commented yesterday
• ... it's even more trivial. And this gives a uniform sequence of circuits; for a nonuniform sequence, you can trivially do it in depth 1 and size $n$, as Benjamin Kuykendall wrote. Commented yesterday