<p>I have asked many experts essentially this question, and the answer I always get is: none.  Diagonalization proofs obviously use uniformity, and these are at the heart of the time and space hierarchy theorems, as well as Fortnow-Williams type of time-space lower bounds.  As far as I know, all the other lower bounds we know of, both for complexity class separations and for data structures, seem to be non-uniform.  It would be great to hear that I'm wrong though :).</p>

CC BY-SA 2.5
2010-08-17T03:20:12.223Z
2010-08-17T03:20:12.223Z
Joshua Grochow
<p>I have asked a few experts and they told me that they think that Eric Allender's
proof that the permanent is not reducible to $TC^0$ makes essential
use of uniformity. See "<a href="http://ftp.cs.rutgers.edu/pub/allender/threshold.pdf" rel="nofollow">The Permanent Requires Large Uniform Threshold Circuits</a>".</p>

<p>Allender cites "<a href="http://www.iro.umontreal.ca/~mckenzie/camcthvo97.ps" rel="nofollow">Nondeterministic $NC^1$ Computation</a>" by Caussinus, McKenzie, Therien, and Vollmer for proving "there are problems in the counting hierarchy that require superpolynomial-size <em>uniform</em> $TC^0$ circuits".</p>

CC BY-SA 2.5
2010-09-16T06:29:55.287Z
From what I understand the proof does finally use diagonalization. The proof assumes the negation of what we want to prove, and then concludes that P = EXP, which is false because they can be separated by diagonalization.
Robin Kothari
CC BY-SA 2.5
2010-09-16T05:17:21.330Z
2010-09-17T07:39:04.807Z
2010-09-17T07:39:04.807Z
Kaveh
<p>This is just a quibble, but as you allude to in your question, it's the simulation that requires uniformity, not the diagonalization per se.  So if I understand your question, that would also include something like Savitch's theorem, which uses simulation but not diagonalization.  Conversely, you could hypothetically have a diagonalization that doesn't make use of simulation.  (I don't know if that is of any practical use, but I know there's been some work along those lines including a classic paper by Kozen.)</p>

CC BY-SA 2.5
2010-08-20T23:35:18.377Z
Thanks for the pointers!  I was reading the journal version of the Kozen paper a few days ago: http://dx.doi.org/10.1016/0304-3975(80)90017-1
András Salamon
CC BY-SA 2.5
2010-08-18T16:47:28.463Z
Which of Kozen's classic papers do you mean?
András Salamon
CC BY-SA 2.5
2010-08-18T19:52:51.393Z
The Kozen paper is "Indexing of subrecursive classes" (http://portal.acm.org/citation.cfm?id=804358)  You might also want to take a look at "Universal Languages and the Power of Diagonalization" by Nash, Impagliazzo and Remmel (http://www.nashalan.com/ccc03-diag2.pdf).
Kurt
CC BY-SA 2.5
2010-08-17T03:55:45.090Z
2010-08-17T03:55:45.090Z
Kurt
<p>We suspect Permanent requires superpolynomial-size circuits (in either of the arithmetic or Boolean models).  However, if we consider Boolean circuits with threshold gates, currently we can only prove superpoly lower bounds in the case of depth-restricted, <em>uniform</em> circuits.  I believe the most recent reference for results of this type is</p>

<p>"A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent"
by Koiran and Perifel.</p>

<p>(Their proof involves diagonalization at some point, so this doesn't strictly speaking meet your criterion, but I thought it might still be of interest.)</p>

CC BY-SA 2.5
2010-09-16T05:22:48.013Z
Here is a link to Koiran and Perifel [paper](http://arxiv.org/abs/0902.1866) on arXive.
Kaveh
CC BY-SA 2.5
2010-08-18T16:18:13.267Z
2010-08-18T16:18:13.267Z
Andy Drucker
<p>A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like time and space hierarchy theorems) make essential use of uniformity as they need to simulate the programs in the smaller class. </p>

<blockquote>
  <p>Which results in complexity theory (other than diagonalization proofs) use uniformity essentially?</p>
</blockquote>

CC BY-SA 2.5
2010-10-07T04:32:28.280Z
It seems that we don't know any such result, so it seems that Joshua Grochow's answer is correct. On the other hand, I found the paper in Andy Ducker's answer interesting, so I am accepting his answer, although it uses diagonaliztion.
Kaveh
<cc.complexity-theory>
Which results in complexity theory make essential use of uniformity?
Kaveh
# Which results in complexity theory make essential use of uniformity?

(Asked by: username_0 on 2010-08-17)

A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like time and space hierarchy theorems) make essential use of uniformity as they need to simulate the programs in the smaller class.

> Which results in complexity theory (other than diagonalization proofs) use uniformity essentially?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_0**: It seems that we don't know any such result, so it seems that Joshua Grochow's answer is correct. On the other hand, I found the paper in Andy Ducker's answer interesting, so I am accepting his answer, although it uses diagonaliztion.  

---

## 4 answers

### Answer by username_5 on 2010-08-18. Score: 6 | Accepted answer

We suspect Permanent requires superpolynomial-size circuits (in either of the arithmetic or Boolean models). However, if we consider Boolean circuits with threshold gates, currently we can only prove superpoly lower bounds in the case of depth-restricted, *uniform* circuits. I believe the most recent reference for results of this type is

"A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent"
by Koiran and Perifel.

(Their proof involves diagonalization at some point, so this doesn't strictly speaking meet your criterion, but I thought it might still be of interest.)

> **Comments:**
> **username_0**: Here is a link to Koiran and Perifel [paper](http://arxiv.org/abs/0902.1866) on arXive.  

---

### Answer by username_1 on 2010-08-17. Score: 12

I have asked many experts essentially this question, and the answer I always get is: none. Diagonalization proofs obviously use uniformity, and these are at the heart of the time and space hierarchy theorems, as well as Fortnow-Williams type of time-space lower bounds. As far as I know, all the other lower bounds we know of, both for complexity class separations and for data structures, seem to be non-uniform. It would be great to hear that I'm wrong though :).


---

### Answer by username_0 on 2010-09-16. Score: 4

I have asked a few experts and they told me that they think that Eric Allender's
proof that the permanent is not reducible to $TC^0$ makes essential
use of uniformity. See "[The Permanent Requires Large Uniform Threshold Circuits](http://ftp.cs.rutgers.edu/pub/allender/threshold.pdf)".

Allender cites "[Nondeterministic $NC^1$ Computation](http://www.iro.umontreal.ca/~mckenzie/camcthvo97.ps)" by Caussinus, McKenzie, Therien, and Vollmer for proving "there are problems in the counting hierarchy that require superpolynomial-size *uniform* $TC^0$ circuits".

> **Comments:**
> **username_2**: From what I understand the proof does finally use diagonalization. The proof assumes the negation of what we want to prove, and then concludes that P = EXP, which is false because they can be separated by diagonalization.  

---

### Answer by username_3 on 2010-08-17. Score: 3

This is just a quibble, but as you allude to in your question, it's the simulation that requires uniformity, not the diagonalization per se. So if I understand your question, that would also include something like Savitch's theorem, which uses simulation but not diagonalization. Conversely, you could hypothetically have a diagonalization that doesn't make use of simulation. (I don't know if that is of any practical use, but I know there's been some work along those lines including a classic paper by Kozen.)

> **Comments:**
> **username_4**: Which of Kozen's classic papers do you mean?  
> **username_3**: The Kozen paper is "Indexing of subrecursive classes" (http://portal.acm.org/citation.cfm?id=804358)  You might also want to take a look at "Universal Languages and the Power of Diagonalization" by Nash, Impagliazzo and Remmel (http://www.nashalan.com/ccc03-diag2.pdf).  
> **username_4**: Thanks for the pointers!  I was reading the journal version of the Kozen paper a few days ago: http://dx.doi.org/10.1016/0304-3975(80)90017-1  

---

