Communications of the ACM

fortunately are not homogeneous anymore and actually have very large degrees). It is difficult to explain to non-experts why this is so unexpected, but as before it carries the same message: proving nω(√n) lower bound for computing the permanent even on depth- 3 arithmetic circuits would separate VP from VNP.

Again, for optimists, this means that we are extremely close to resolving a major goal of the field. For pessimists, this may be simply an indication of how strong are depth- 3 circuits and how hopeless proving lower bounds is even for them. I am on the optimists’ side. As far as we know, in the arithmetic setting we have no barriers (aka excuses) of the “natural proofs” or “relativization” varieties, which seem to explain our failure so far to prove lower bounds in the Boolean setting. Moreover, the arithmetic setting is making good on the promise of providing mathematical techniques, which may help resolve its major problems, as the line of work here indicates. Another indication, of course, the Geometric Complexity Theory (GCT) approach of Mulmuley and Sohoni, 5 which approaches the VP vs. VNP question from a different direction, based on invariant theory and representation theory. Indeed, some relations and connections between the two approaches were discovered, and the growing interests of pure mathematicians in these computational complexity questions is encouraging.

As we have grown to expect of
computational complexity, there are
myriad connections of this research
in arithmetic complexity to other
seemingly distinct subareas of the
field. One important connection to
pseudorandomness, in particular
the intimate relationship between
derandomizing the probabilistic
algorithm for Polynomial Identity
Testing (PIT) and arithmetic lower
bounds discovered by Kabanets and
Impagliazzo. 4 Subsequently, Dvir
and Shpilka2 initiated a program to
understand this question for very
shallow circuits, making connec-
tions to locally decodable and cor-
rectable codes on the one hand and
to combinatorial geometry (mainly
incidence theory) on the other. This
has lead to a long sequence of papers
obtaining both new lower bounds
and new identity testing algorithms
for larger and larger classes of low-
depth and other circuit models. Yet
another exciting connection was re-
cently made by Grochow and Pitassi3
between arithmetic complexity, PIT
and proof complexity, in what will
surely develop and possibly lead to
lower bounds in that field.

Let me conclude with a riddle: Can depth- 3 lower bounds on Boolean circuits lead to “real” lower bounds, as they do in the arithmetic setting? Yes! The positive answer in Valiant’s7 predates all of these developments. In this paper Valiant shows that any function requiring exp(n) size depth- 3 Boolean circuits cannot be computed by a linear-size, logarithmic depth circuit. The state-of-art in Boolean circuit lower bounds is so pathetic that the latter remained one of its major goals since Valiant’s paper, and can be achieved via strong enough depth- 3 lower bounds.

On to proving real lower bounds!

References

1. Agrawal, M. and Vinay, V. Arithmetic circuits: A chasm at depth four. In Proceedings of the Annual Symposium on Foundations of Computer Science.

IEEE, 2008, 67–75.

2. Dvir, Z. and Shpilka, A. Locally decodable codes with two queries and polynomial identity testing for depth

3 circuits. SIAM Journal on Computing 36, 5 (2007),

1404–1434.

3. Grochow, J. et al. Circuit complexity, proof complexity, and polynomial identity testing. In Proceedings of IEEE 55th Annual Symposium Foundations of Computer Science. IEEE, 2014, 110–119.

4. Kabanets, V. and Impagliazzo, R. Identity tests means proving circuit lower bounds. Comput. Complexity 13,

1–2 (2004), 1–46.

5. Mulmuley, K. and Sohoni, M. Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM J. Comput. 31, 2 (201), 496–526.

6. Nisan, N. and Wigderson, A. Lower bounds on arithmetic circuits via partial derivatives.

Computational Complexity 6, 3 (1996), 217–234.

7. Valiant, L.G. Graph-theoretic arguments in low-level complexity. Springer, 1977.

8. Valiant L. G. Completeness classes in algebra. In

Proceedings of the 11th Annual ACM Symposium on Theory of Computing, (1979), 249–261.

9. Valiant. L.G., Skyum, S., Berkowitz S., and Rackoff, C. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing 12, 4 (1983), 641–644.

Avi Wigderson is a professor in the School of Mathematics, Institute for Advanced Study, at Princeton University, Princeton, NJ.

Copyright held by author.

ACM Conference
Proceedings
Now Available via
Print-on-Demand!

Did you know that you can
now order many popular
ACM conference proceedings
via print-on-demand?

Institutions, libraries and individuals can choose from more than 100 titles on a continually updated list through Amazon, Barnes & Noble, Baker & Taylor, Ingram and NACSCORP: CHI, KDD, Multimedia, SIGIR, SIGCOMM, SIGCSE, SIGMOD/PODS, and many more.