Tuesday, November 09, 2010

A Breakthrough Circuit Lower Bound

On October 8th, when in my graduate complexity course as we discussed the 1987 Razborov-Smolensky result that one can't compute the Modp by constant-depth polynomial-size circuits with AND, OR, NOT and Modq gates for primes p≠q, I noted the limits of our knowledge,
We can't even prove that NEXP (the exponential time version of NP) can't be solved by constant-depth polynomial-size circuits with just Mod6 gates, even without AND and ORs.
Now we can. And by "we" I mean Ryan Williams who just yesterday posted his proof that NEXP cannot be solved in the class ACC0, the class of constant-depth poly-size circuits with AND, OR, NOT and Modm gates for any fixed m. For the larger class EXPNP, Ryan gets exponential lower bounds. Dick, Scott and Luca already heaped their praise on these new results. No doubt, this is perhaps the most interesting computational complexity result since Reingold and the best progress in circuit lower bounds in nearly a quarter century.

It's not so much the result itself, in class I'll now just say "We don't even know how to prove that NEXP isn't in TC0 (poly-size constant-depth circuits with majority gates)" but an outright example that the proof techniques described in Ryan's STOC paper can be used to get new lower bounds, really opening the door to the first fresh approach to circuits in a long time. This approach converts weak algorithms for solving circuit satisfiability questions into circuit lower bounds. Ryan's proof doesn't use deep mathematical techniques but rather puts together a series of known tools in amazingly clever ways.

Ryan breaks through the natural proofs barrier in an interesting way. We didn't know if one can have one-way functions described by ACC0 circuits so it wasn't clear if natural proofs applied to lower bounds for ACC0. Ryan's paper doesn't break these one-way functions, rather he avoids the issue by using diagonalization and so his proof does not fulfill the constructivity requirement of natural proofs. Modifying his proof to make it "natural" would imply showing there aren't ACC0 one-way functions but that's still open. So there is no inherent reason Ryan's techniques couldn't work on TC0 or larger classes without violating natural proofs.

We're still a long long long way from showing NP does not have arbitrary polynomial-size circuits and P ≠ NP but Ryan has taken the first real baby step in decades.

10 comments:

  1. What a wonderful result. As a small aside, we actually think we do have one-way functions in ACC0 (and even NC0), I believe the open question is regarding pseudorandom functions.

    ReplyDelete
  2. Maybe a silly question, but is anything known about what happens to the class ACC^0 if we allow mod_m gates and mod_n gates for two distinct m, n?

    ReplyDelete
  3. For mod_m and mod_n with different m and n, we can replace the two types of gates with one gate mod_(mn).

    ReplyDelete
  4. Anonymous: ACC^0 supports multiple moduli. You can simulate mod_m and mod_n with mod_{m*n}. So as long as there are a constant number of such moduli, ACC^0 remains the same.

    ReplyDelete
  5. Anonymous 3: Razborov-Smolensky already showed that modp can't be computed by ACC with modq gates for p \neq q distinct primes. (And so NEXP is not in ACC with modp gates for p prime.) 6 is the smallest product of distinct primes.

    ReplyDelete
  6. What is NEXP? Could someone describe what just happened on a slightly less technical level?

    ReplyDelete
  7. He uses "diagonalization", and we're calling that progress? Umm, no. Try again. Non-constructive proofs aren't worth the paper they're printed on.

    ReplyDelete
  8. I second the last "Anonymous": where is the hard function? To call circuit lower bounds obtained by diagonalization and counting "breakthrough" seems somewhat too generous ... I don't say the result is not interesting: it is! But not in the same level with, say, Razborov's *explicit* lower bounds.

    ReplyDelete
  9. One thing I find worth noticing in the blog post is the statement:

    "Ryan's proof doesn't use deep mathematical techniques but rather puts together a series of known tools in amazingly clever ways."

    Cleverness is often a key to breakthroughs in algorithm: sometimes a small twist makes a huge difference. However, some referees seem to think that papers need to have fundamental new technique: that a strong result doesn't do it.

    ReplyDelete