Information Technology Reference
In-Depth Information
via radicals of a quintic, Lagrange's theorem on expressing every natural number
as a sum of four squares and the impossibility of trisecting an angle (using ruler
and compass). In modern times, computer scientists have begun to investigate as to
what functions can be (efficiently) computed. Polynomials being a natural class of
functions, one is naturally led to the following question:
What is the optimum way to compute a given (family of) polynomial(s)?
Now the most natural way to compute a polynomial
f
(
x
1
,
x
2
,...,
x
n
)
over a field
F
x
n
and then apply a sequence of basic
operations such as additions, subtractions, and multiplications
1
in order to obtain the
desired polynomial
f
. Such a computation is called a straight-line program. We
often represent such a straight-line program graphically as an arithmetic circuit—
wherein the overall computation corresponds to a directed acylic graph whose source
nodes are labelled with the input variables
is to start with the input variables
x
1
,
x
2
,...,
{
x
1
,
x
2
,...,
x
n
}
and the internal nodes
are labelled with either
(each internal node corresponds to one computational
step in the straight-line program). We typically allow arbitrary constants from the
underlying field on the incoming edges of a
+
or
×
+
gate so that a
+
gate can in fact compute
an arbitrary
-linear combination of its inputs. The complexity of the computation
corresponds to the number of operations, also called the size of the corresponding
arithmetic circuit. With arithmetic circuits being the relevant model, the informal
question posed above can be formalized by defining the optimal way to compute a
given polynomial as the smallest arithmetic circuit in terms of the size that computes
it. While different aspects of polynomials have been studied extensively in various
areas of mathematics, what is unique to computer science is the endeavor to prove
upper and lower bounds on the size of arithmetic circuits computing a given (family
of) polynomials. Here we give a biased survey of this area, focusing mostly on
lower bounds. Note that there are already two excellent surveys of this area—one
by Avi Wigderson [
Wig02
] and the other by Amir Shpilka and Amir Yehudayoff
[
SY10
].
2
Our intention in writing the survey is the underlying hope that revisiting and
assimilating the known results pertaining to circuit lower bounds will in turn help us
make progress on this beautiful problem. Consequently, we mostly present here those
resultswhichwe for some reason felt we did not understand comprehensively enough.
We conclude with some recent lower bound results for homogeneous bounded depth
formulas. Some notable lower bound results that we are unable to present here due
to space and time constraints are as follows. A quadratic lower bound for depth
three circuits by Shpilka and Wigderson [
SW01
], for bounded occur bounded depth
formulas by Agrawal, Saha, Saptharishi, and Saxena [
ASSS12
] and the
n
1
+
ˇ(
1
/
r
)
lower bound for circuits of depth
r
by Raz [
Raz10
].
F
1
One can also allow more arithmetic operations such as division and square roots. It turns out,
however, that one can efficiently simulate any circuit with divisions and square roots by another
circuit without these operations while incurring only a polynomial factor increase in size.
2
A more specialized survey by Chen, Kayal, and Wigderson [
CKW11
] focuses on the applications
of partial derivatives in understanding the structure and complexity of polynomials.
