Constraints

9 November 2010

New ACC circuit lower bounds

Filed under: Commentary — András Salamon @ 17:25
Tags:

Ryan Williams recently published a draft proving new lower bounds for ACC circuits. ACC (often known as ACC0) is the class of constant depth circuits with unbounded fan-in gates, where the usual AND/OR/NOT gates are supplemented by MODm gates for some constant m.

Furst, Saxe, and Sipser in 1981 and Ajtai in 1983 showed that there were functions that cannot be computed by constant depth, polynomial size circuits over AND, OR, and NOT gates. These results were strengthened by Yao in 1985. Razborov in 1985 also showed that monotone circuits (using AND and OR gates only) to solve CLIQUE must be of superpolynomial size, later extended to exponential lower bounds. Hopes were raised for further circuit lower bounds, but then Razborov and Rudich in 1996 showed that there were big obstacles to making progress. Their landmark paper made precise a notion of natural proofs, which includes all proof attempts up to that point, and also captures the most straightforward proof strategy. The main result was that natural proofs cannot prove strong circuit lower bounds unless some surprising things are true. The effective prohibition on natural proofs discouraged research into circuit lower bounds for a decade. (In retrospect, this in rather reminiscent of the Minsky/Papert proof in 1969 that perceptrons cannot represent all functions. This discouraged neural networks research for over ten years.)

Benjamin Rossman showed an exponential size lower bound for fixed-depth circuits in 2008, in a breakthrough result. It is good to see continued progress in circuit lower bounds. In particular, Ryan Williams showed that NTIME[2n] does not have non-uniform ACC circuits of polynomial size, and also showed that there are languages in ENP that do not have non-uniform ACC circuits of subexponential size. (Note that it is still possible that allowing unbounded depth might allow subexponential size circuits). Perhaps these techniques can be extended to separate Note that this separates EXPNP and AC0[6]. This is was a long-standing open problem that would be one of the “small” consequences of proving P ≠ NP, and is was therefore seen as an important step in such a proof.

Edit 2010-11-10: corrected the implications of the result.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: