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.
For available titles and
ordering info, visit:
librarians.acm.org/pod
ACM Conference
Proceedings
Now Available via
Print-on-Demand!