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.
Advertisement
Like this:
One blogger likes this post.
New ACC circuit lower bounds
Tags: papers
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 separateNote that this separates EXPNP and AC0[6]. Thisiswas a long-standing open problem that would be one of the “small” consequences of proving P ≠ NP, andiswas therefore seen as an important step in such a proof.Edit 2010-11-10: corrected the implications of the result.
Like this: