<p>Here are answers to your last two questions.</p>

<p>(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). [<a href="http://dl.acm.org/citation.cfm?doid=800061.808726">AKS83</a>,<a href="http://arxiv.org/abs/1403.2777">G14</a>]</p>

<p>(4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon&gt;0$, but for a silly reason: Every function is computed by a circuit of size $(1+o(1)) \cdot 2^n/n$. (<a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6771698">Shannon</a> proved this up to a constant and <a href="http://en.wikipedia.org/wiki/Oleg_Lupanov">Lupanov</a> 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 <i>think</i> 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)$.</p>

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

CC BY-SA 3.0
2014-06-07T01:41:05.190Z
Thanks, you're right, I intuitively wanted to rule out this "upper-bounding" case but didn't know the right asymptotic. I've edited the question to include that case.
usul
CC BY-SA 3.0
2014-06-06T16:45:29.267Z
2014-06-06T16:51:17.530Z
2014-06-06T16:51:17.530Z
Thomas Steinke
<p>Given an algorithm running in time <span class="math-container">$t(n)$</span>, we can convert it into a &quot;trivial&quot; uniform circuit family for the same problem of size at most <span class="math-container">$\approx t(n)\log t(n)$</span>.</p>
<p>On the other hand, it might be that we have much smaller uniform circuits for that problem, even if <span class="math-container">$t(n)$</span> is an optimal running time. The circuits may take longer than <span class="math-container">$t(n)$</span> to generate, but they are small.</p>
<p>But do we actually know how to build such things? I think the initial question to ask is</p>
<blockquote>
<p>(1) Do we have any constructive examples of nontrivial uniform circuits, <em>i.e.</em> uniform circuits whose size is smaller than the best-known running time of any algorithm for the same problem?</p>
</blockquote>
<p>Now, I believe that if a problem is in <span class="math-container">$\mathsf{DTIME(t(n))}$</span>, then we have an exponential-time algorithm to find optimal circuits using an exhaustive search: Given <span class="math-container">$n$</span>, we write down the answers on all <span class="math-container">$2^n$</span> inputs (taking time <span class="math-container">$(2^n)t(n)$</span>); then we enumerate all circuits on <span class="math-container">$n$</span> 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, <span class="math-container">$t(n) \log t(n)$</span>, or the truth table of the function, <span class="math-container">$2^n$</span> if outputs are <span class="math-container">$\{0,1\}$</span>. (Edit: Thomas points out that the bound is <span class="math-container">$O(2^n/n)$</span> due to Shannon/Lupanov.)</p>
<p>So we have an unsatisfactory &quot;yes&quot; to question (1): Take a language that is hard for any time above <span class="math-container">$2^n$</span>, but still decidable; the above procedure outputs a truth table of size <span class="math-container">$2^n$</span>.</p>
<p>So we should refine question (1). I think the two most interesting cases are</p>
<blockquote>
<p>(2) Do we have any constructive examples of <em>polynomial-size</em> nontrivial uniform circuits? (Even if they are generated by very slow algorithms.)</p>
<p>(3) Do we have any constructive examples of <em>polynomial-time generatable</em>, polynomial-size nontrivial uniform circuits?</p>
</blockquote>
<p>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?</p>
<blockquote>
<p>(4) Is the following statement known to be false for any <span class="math-container">$s(n) = o(2^n)$</span>? (Edit: <span class="math-container">$o(2^n/n)$</span>, thanks Thomas.) &quot;If a language <span class="math-container">$L$</span> has uniform circuits of size <span class="math-container">$O(s(n))$</span>, then it also has algorithms running in time <span class="math-container">$\tilde{O}(s(n))$</span>.&quot; (If so, then what about when &quot;uniform&quot; is replaced with &quot;polynomial-time-uniform&quot;, &quot;logspace uniform&quot;, etc?)</p>
</blockquote>
<p>Finally, if the above questions are too hard,</p>
<blockquote>
<p>(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)?</p>
</blockquote>
<p>Postscript. An expert I asked about this mentioned &quot;On Medium-Uniformity and Circuit Lower Bounds&quot; (<a href="http://www.stanford.edu/%7Errwill/WeakUniformityCCC.pdf" rel="noreferrer">pdf</a>), Santhanam and Williams 2013, which maybe is the most closely related work, but it proves lower bounds (that poly-time-generatable circuits are not <em>too</em> powerful). I'd be interested in any other related work!</p>

CC BY-SA 3.0
2014-06-06T09:25:37.113Z
1,2,3,4: Identity function. 5. it is not clear to me what you mean by "being a conversion of algorithms into circuits", we can always convert a uniform circuit into a Turing machine (with a small overhead).
Kaveh
CC BY-SA 3.0
2014-06-06T12:42:21.537Z
@Kaveh, re #5: Good point, but I guess what I have in mind is someone writing down an explicit construction of uniform circuits, that does not look like "convert this TM into a circuit". Also, I think the conversion you mention might not really mean that the circuit "looks like" an algorithm. E.g, say we have a size-$n$ circuit that takes $n^3$ time to generate. We can turn it into a time-$n^3$ TM, ok, but it doesn't resemble the circuit very much, and the naive conversion of that TM back into a circuit is now of size ~ $n^3$. I hope this shows why the question interests me.
usul
CC BY-SA 3.0
2014-06-06T16:34:09.150Z
@Kaveh: How does the identity function answer 1-4?
Joshua Grochow
CC BY-SA 3.0
2014-06-06T20:44:26.210Z
@Joshua, we can directly describea a uniform circuit of (wire) size O(n), which is better than the conversion of the Turing machine for identity to a circuit.
Kaveh
CC BY-SA 3.0
2014-06-06T21:05:16.733Z
My point is there are important small details the we need to care about to make the question answerable. Another example: BPP is in P/poly and the conversion is computable. If the circuit  generation is done by an efficient algorithm combining it with circuit value will give an efficient TM. Conceptually the circuit and the TM compute the same algorithm. The fact that size and time may not correspond exactly is normal, they are defined for different computation models and we know they don't correspond. Arguably time corresponds more to depth than to size.
Kaveh
CC BY-SA 3.0
2014-06-07T14:43:35.750Z
too many questions, suggest splitting them... _agreed_ with K.s challenge. uniform circuits and TM lower bounds are basically interchangeable within exactly or nearly constant factors (ie big-Oh bounds), right? so the question about _uniform_ circuits seems somewhat superfluous, it might as well just ask about any lower bounds (afaik no unrestricted/nonuniform lower bounds have ever been proven lower than uniform bounds, right?). the questions also seem to miss connection between proofs/algorithms, re Curry-Howard correspondence there exist no proofs that cannot be converted into algorithms.
vzn
CC BY-SA 3.0
2014-06-07T15:04:47.253Z
??? re (2)/(3) are these lower or upper bounds? arent _all_ algorithms in P sufficient? also the construction in the time hierarchy theorem mentioned in Thomas answer (basically enumerating/universally simulating TMs with "clocks") can even generate/enumerate _all_ such languages... suggest juknas excellent ref [boolean circuit complexity](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/) for survey in this overall area...
vzn
CC BY-SA 3.0
2014-06-07T17:16:50.910Z
@Kaveh, as I mentioned above, we might have "small" circuits that look *nothing* like TMs for the same problem. (Or we might not...?) The fact that one could generate these circuits in polynomial time doesn't change that their structure would be fundamentally different from "trivial" converted-TM circuits. Time vs size isn't so important here; the point is they let us capture "triviality" vs "non-triviality".
usul
CC BY-SA 3.0
2014-06-07T17:17:41.400Z
@vzn, (2)/(3) are asking for upper bounds, i.e. answers to (5) that are also asymptotically better than the best known trivial-conversion-of-a-TM.
usul
<cc.complexity-theory><circuit-complexity><uniformity>
Do we have any nontrivial uniform circuits?
usul
# Do we have any nontrivial uniform circuits?

(Asked by: username_0 on 2014-06-06)

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](http://www.stanford.edu/%7Errwill/WeakUniformityCCC.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!

**Tags:** cc.complexity-theory, circuit-complexity, uniformity
> **Comments:**
> **username_1**: 1,2,3,4: Identity function. 5. it is not clear to me what you mean by "being a conversion of algorithms into circuits", we can always convert a uniform circuit into a Turing machine (with a small overhead).  
> **username_0**: @Kaveh, re #5: Good point, but I guess what I have in mind is someone writing down an explicit construction of uniform circuits, that does not look like "convert this TM into a circuit". Also, I think the conversion you mention might not really mean that the circuit "looks like" an algorithm. E.g, say we have a size-$n$ circuit that takes $n^3$ time to generate. We can turn it into a time-$n^3$ TM, ok, but it doesn't resemble the circuit very much, and the naive conversion of that TM back into a circuit is now of size ~ $n^3$. I hope this shows why the question interests me.  
> **username_2**: @Kaveh: How does the identity function answer 1-4?  
> **username_1**: @Joshua, we can directly describea a uniform circuit of (wire) size O(n), which is better than the conversion of the Turing machine for identity to a circuit.  
> **username_1**: My point is there are important small details the we need to care about to make the question answerable. Another example: BPP is in P/poly and the conversion is computable. If the circuit  generation is done by an efficient algorithm combining it with circuit value will give an efficient TM. Conceptually the circuit and the TM compute the same algorithm. The fact that size and time may not correspond exactly is normal, they are defined for different computation models and we know they don't correspond. Arguably time corresponds more to depth than to size.  
> **username_3**: too many questions, suggest splitting them... _agreed_ with K.s challenge. uniform circuits and TM lower bounds are basically interchangeable within exactly or nearly constant factors (ie big-Oh bounds), right? so the question about _uniform_ circuits seems somewhat superfluous, it might as well just ask about any lower bounds (afaik no unrestricted/nonuniform lower bounds have ever been proven lower than uniform bounds, right?). the questions also seem to miss connection between proofs/algorithms, re Curry-Howard correspondence there exist no proofs that cannot be converted into algorithms.  
> **username_3**: ??? re (2)/(3) are these lower or upper bounds? arent _all_ algorithms in P sufficient? also the construction in the time hierarchy theorem mentioned in Thomas answer (basically enumerating/universally simulating TMs with "clocks") can even generate/enumerate _all_ such languages... suggest juknas excellent ref [boolean circuit complexity](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/) for survey in this overall area...  
> **username_0**: @Kaveh, as I mentioned above, we might have "small" circuits that look *nothing* like TMs for the same problem. (Or we might not...?) The fact that one could generate these circuits in polynomial time doesn't change that their structure would be fundamentally different from "trivial" converted-TM circuits. Time vs size isn't so important here; the point is they let us capture "triviality" vs "non-triviality".  
> **username_0**: @vzn, (2)/(3) are asking for upper bounds, i.e. answers to (5) that are also asymptotically better than the best known trivial-conversion-of-a-TM.  

---

## 1 answers

### Answer by username_4 on 2014-06-06. Score: 8

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](http://dl.acm.org/citation.cfm?doid=800061.808726),[G14](http://arxiv.org/abs/1403.2777)]

(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](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6771698) proved this up to a constant and [Lupanov](http://en.wikipedia.org/wiki/Oleg_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).

> **Comments:**
> **username_0**: Thanks, you're right, I intuitively wanted to rule out this "upper-bounding" case but didn't know the right asymptotic. I've edited the question to include that case.  

---

