Do we have any nontrivial uniform circuits?

Question

Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$.

On the other hand, it might be that we have much smaller uniform circuits for that problem, even if $t(n)$ is an optimal running time. The circuits may take longer than $t(n)$ to generate, but they are small.

But do we actually know how to build such things? I think the initial question to ask is

(1) Do we have any constructive examples of nontrivial uniform circuits, i.e. uniform circuits whose size is smaller than the best-known running time of any algorithm for the same problem?

Now, I believe that if a problem is in $\mathsf{DTIME(t(n))}$, then we have an exponential-time algorithm to find optimal circuits using an exhaustive search: Given $n$, we write down the answers on all $2^n$ inputs (taking time $(2^n)t(n)$); then we enumerate all circuits on $n$ inputs in increasing size until one is found that gives all the correct answers. The search terminates at either the size of the trivial conversion, $t(n) \log t(n)$, or the truth table of the function, $2^n$ if outputs are $\{0,1\}$. (Edit: Thomas points out that the bound is $O(2^n/n)$ due to Shannon/Lupanov.)

So we have an unsatisfactory "yes" to question (1): Take a language that is hard for any time above $2^n$, but still decidable; the above procedure outputs a truth table of size $2^n$.

So we should refine question (1). I think the two most interesting cases are

(2) Do we have any constructive examples of polynomial-size nontrivial uniform circuits? (Even if they are generated by very slow algorithms.)

(3) Do we have any constructive examples of polynomial-time generatable, polynomial-size nontrivial uniform circuits?

This may be too much to ask. How about an easier question: Do we even know that such a thing is possible? Perhaps no nontrivial uniform circuits exist?

(4) Is the following statement known to be false for any $s(n) = o(2^n)$? (Edit: $o(2^n/n)$, thanks Thomas.) "If a language $L$ has uniform circuits of size $O(s(n))$, then it also has algorithms running in time $\tilde{O}(s(n))$." (If so, then what about when "uniform" is replaced with "polynomial-time-uniform", "logspace uniform", etc?)

Finally, if the above questions are too hard,

(5) Do we have any constructions of uniform families of circuits that are not simply conversions of algorithms into circuits (or writing down the truth table)?

Postscript. An expert I asked about this mentioned "On Medium-Uniformity and Circuit Lower Bounds" (pdf), Santhanam and Williams 2013, which maybe is the most closely related work, but it proves lower bounds (that poly-time-generatable circuits are not too powerful). I'd be interested in any other related work!

Answer 1

Here are answers to your last two questions.

(5) Sorting networks are uniform circuits that sort as fast as the best RAM algorithms, but are definitely not just conversions of RAM algorithms (e.g. quicksort). [AKS83,G14]

(4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon>0$, but for a silly reason: Every function is computed by a circuit of size $(1+o(1)) \cdot 2^n/n$. (Shannon proved this up to a constant and Lupanov got the optimal constant.) By the time hierarchy theorem, there exists a function $f$ with uniform time complexity between $\Omega(3^n)$ and $O(n \cdot 3^n)$. This gives a counterexample: $f$ has circuits of size $O(2^n/n)$ (which I think are computable in $2^{\mathrm{poly}(n)}$ time) but is not computable in $\tilde{O}(2^n/n)$ time. You should probably ask for $s(n) = o(2^n/n)$.

This is an interesting question; I hope someone can answer (1)-(3).