Succinct Constant Depth Arithmetic Circuits Are Weak

Maurice Jansen has spent the past few years helping push back the frontiers of complexity theory. His penetrating work is revealing the structure of what makes a problem hard, and could lead to the breakthrough that we all are looking for.

Today we would like to discuss recent work that he has done in his current postdoc with Rahul Santhanam, whom we mentioned recently here. Their paper will appear in the proceedings of the 38th ICALP conference, July 4–8 in Zürich, Switzerland. It is exciting work that uses methods that we feel are—and will continue to be—central to finding lower bounds.

Perhaps one of the reasons he has been so successful is that he has also pushed hard on the physical frontiers of theory. Even in the age of the Internet, physical presence means a lot. Maurice has traveled from Russia to China to India, working with some top researchers and getting papers into these countries’ main theory conferences. He also organized a workshop on algebraic complexity while at Aarhus with Peter Bro Miltersen, at which Manindra Agrawal, Pascal Koiran, and Ketan Mulmuley were plenary speakers giving multiple talks. No doubt he has helped make complexity theory more global. The more who think hard about our great problems, the better.

In particular, Maurice has held a postdoc at Tsinghua University in Beijing, at the Institute for Theoretical Computer Science which was co-founded by Andy Yao. Maurice has also visited India where he worked with B.V. Raghavendra Rao and Jayalal Sarma, both students of Meena Mahajan. Globetrotting along with Maurice have been his wife Cathy and their young child. They toured some of the beautiful sights of China, including Xi’an of the famous Terracotta Warriors.

Wherever he is, Maurice has been squarely devoted to difficult problems of lower bounds against families of constant depth arithmetical circuits. Some of this work has been alone and some joint. We might not consider ICALP in Zürich to be as exotic as his other travels, but Switzerland has been “frontier” territory in wars from Hannibal to WW II.

The Frontiers

Let “exponential” size mean size for some , let “fully exponential” refer to size , and let “demi-exponential” mean size where , or , or some finite iteration , is exponential—it is like a demitasse, a half cup. We ignore NOT gates at the inputs. Well we do not ignore them, they are very impotant gates, but we do not count them in the size of a circuit. Arithmetical circuits can have unbounded fan-in and gates, and besides the input gates, can have gates with fixed numerical constants.

The current frontiers of what is known about lower bounds are:

1. Constant-depth circuits of unbounded fan-in AND and OR gates need exponential size even to compute simple functions such as parity.
2. Constant-depth circuits of Boolean and Mod- gates (for fixed ) need demi-exponential size to compute functions in . This is Ryan Williams’ recent breakthrough result—previously nothing much more was known for these circuits than for the ostensibly more-powerful circuits in the next item.
3. Constant-depth circuits of threshold gates need half-exponential size to compute functions in , which is a “Merlin-Arthur” class that extends . The same is known for any kind of 0-1 logic circuit. Put another way, is the smallest standard complexity class that is known not to have polynomial-size Boolean circuits.
4. Polynomial-size, constant-depth threshold circuits that are uniform, however, cannot compute the permanent (Eric Allender, after his previous work with Vivek Gore). The size lower bound is known to extend only to functions that are not demi-exponential, not for any .
5. For constant-depth arithmetic circuits over the rationals, however, essentially nothing is known.

Indeed, Manindra Agrawal and V. Vinay showed that if the permanent in variables cannot be computed by size arithmetical circuits of depth 4, then it requires size, period. Thus we have the

Arithmetical Frontier: Prove super-polynomial lower bounds on arithmetical circuits of depth 4, or of depth 3.

Indeed there are not even any bounds on depth 3 for the permanent, and none beyond on depth 3 for any polynomial.

Given this state of affairs, what do we do? We have already done some game-changing in going from Boolean to arithmetical circuits. Alternatively, we can look for plausible premises to add, and/or place reasonable restrictions on the circuits. This is the kind of work Maurice has been assiduously doing, ever since his Ph.D. work under Ken which centered on arithmetical circuits whose numerical constants have bounded magnitude. The main new conceptual ingredient is one we have propounded here before.

Enter Succinctness

A string of length is succinct if there is an -input circuit of size , or at least size , such that for all , outputs the bit . A graph is succinct if its edge relation is succinct, i.e., there is a small such that if and only if . A circuit is succinct if its underlying graph is succinct, together with information about the type of a given gate in .

In particular, Maurice and Rahul define a family of arithmetical circuits , each of size , to be succinct if there are Boolean circuits with inputs and size that decide questions of the form:

Is gate connected to gate ? Does it have type ?

Here can designate or for addition and multiplication gates, respectively, or for the th input gate, or one of the allowed constants , , or . Thus these succinct circuits also have bounded constants. However, their notion of succinctness extends to allow also to belong to the double-exponential sequence ; call them spaced constants. They prove:

Theorem: The permanent does not have constant-depth succinct arithmetical circuits of polynomial size.

Note that we are talking about the non-existence of circuits of size whose direct-connection language can be decided by Boolean circuits of size , since and so . For technical reasons their proofs employ bounds where is unbounded but stays . Of course allowing the circuits to have size sub-exponential in their number of inputs is pretty generous, since previously we have thought of the succinct describing circuits as having polynomial size. Thus their work makes a fairly minimal restriction of succinctness, and hence their result is strong.

Using Succinctness

Succinctness is weaker than uniform and more restrictive than general. A uniform family of circuits are all describable by one single algorithm; a succinct family of circuits all have small descriptions, but the description can vary from one to another in any way at all. Of course, a general family of circuits need have no small descriptions, and can vary from one to another in an arbitrary manner.

One challenge that succinct raises over uniform is that if a circuit has a succinct description, then it is possible to guess the description of the much larger circuit. This is very powerful, the ability to guess a much larger object without incurring the cost of writing it down is quite useful. The challenge is: there is no generic way to know that you have guessed correctly. Thus the use of succinctness assumptions requires some checking method to see that the guessed circuit is really the correct one.

Proof Idea

Their proof is clever and exploits a condition we’ll call Hypothesis H asserting the existence of a “nice” table of numbers. From H the theorem follows. Maurice and Rahul do not know how to prove H directly, but they use a proof-by-contradiction method. Denying Theorem 1 causes the nonuniform counting hierarchy to collapse into nonuniform . This collapse is enough to exploit their ability to create a “moderately nice” table in the polynomial hierarchy. On applying the famous theorem of Seinosuke Toda and the proof by Viktória Zankó that the 0-1 permanent is complete for via many-one reductions, the table is good enough to imply Theorem 1 anyway. The only way to resolve this contradiction is for Theorem 1 to be true.

To state H, which is really a family of hypotheses over different constant depths , define the language

Hypothesis H then asserts that there exist polynomial and a function with defined for and to be a string of at most bits, so that the following holds.

• Easy: is decidable by succinct circuits.
• Hitting: For all sufficiently large , for every depth- arithmetic circuit of size with spaced constants, if the polynomial computed by () is not identically zero, then there exists such that

  

Note that the circuit need not be succinct, though it has spaced constants. Nor does H impose a second succinctness assumption as a condition on Theorem 1 itself. Instead what is happening is that denying Theorem 1—i.e. allowing succinct constant-depth arithmetical circuits for the permanent—allows one to find succinct Boolean threshold circuits for , which together with satisfying the hitting condition yields the desired contradiction.

This looks convoluted, since it is; but it is not circular and is quite ingenious. It is the kind of argument that we need to understand better, since it seems very powerful and could lead to great progress on lower bounds.

Further details are bound up with black-box de-randomization of polynomial identity testing, and can be found in the paper. It is a globetrotting tour of major complexity concepts, even more than we’ve mentioned.

Open Problems

Can we better understand the kind of diagonalization that the above notion of hitting represents, and extend Maurice and Rahul’s kind of argument? Can we use it for Boolean as well as arithmetical complexity theory?

Can the restriction on constants be removed from their theorem? Note other lower bounds on arithmetic circuits also require restrictions on constants. Is there really a way to use the size or bit-pattern of constants to “cheat” and decrease the size of a circuit? Jacques Morgenstern’s 1973 lower bound on FFT uses the bounded-constants assumption, and we believe today, over forty years later, there is no proof that relaxes it in any significant way.