21
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 7 '10 at 4:32
6
$\begingroup$

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.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Here is a link to Koiran and Perifel paper on arXive. $\endgroup$ – Kaveh Sep 16 '10 at 5:22
11
$\begingroup$

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 :).

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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.)

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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".

Allender cites "Nondeterministic $NC^1$ Computation" by Caussinus, McKenzie, Therien, and Vollmer for proving "there are problems in the counting hierarchy that require superpolynomial-size uniform $TC^0$ circuits".

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Sep 16 '10 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.