A Selection of Lower Bounds for Arithmetic Circuits - Perspectives in Computational Complexity - page 76

Overview. The state of affairs in arithmetic complexity is such that despite a lot of
attention we still have only modest lower bounds for general circuits and formulas.
In order to make progress, recent work has focused on restricted subclasses. We first
present the best-known lower bound for general circuits due to Baur and Strassen
[ BS83 ], and a lower bound for formulas due to Kalorkoti [ Kal85 ]. The subsequent
lower bounds that we present follow a common roadmap and we articulate this in
Sect. 5.4 , and present some simple lower bounds to help the reader gain familiarity.
We then present (a slight generalization of) an exponential lower bound for monotone
circuits due to Jerrum and Snir [ JS82 ]. Moving on to some other restricted (but still
nontrivial and interesting) models, we first present an exponential lower bound for
depth three circuits over finite fields due to Grigoriev and Karpinski [ GK98 ] and
multilinear formulas. We conclude with some recent progress on lower bounds for
homogeneous depth four circuits.

Remark Throughout the article, we shall use Det n and Perm n to refer to the deter-
minant and permanent, respectively, of a symbolic n n matrix x ij 1 ≥ i , j ≥ n .

×

5.2 Existential Lower Bounds

Before we embark on our quest to prove lower bounds for interesting families of
polynomials, it is natural to ask as to what bounds one can hope to achieve. For
a multivariate polynomial f

( x ) ∗ F[ x ] , denote by S ( f ) the size of the smallest

arithmetic circuit computing f .

Theorem 1 (Folklore) For “most” polynomials f ( x ) ∗ F[ x ] of degree d on n vari-

ables we have

⊡ ⊣ n

⊤ ⊦

+ d

S ( f ) ↆ ˇ .

d

Sketch of Proof We prove this here only in the situation where the underlying field F

is a finite field and refer the reader to another survey ([ CKW11 ], Chap. 4 ) for a proof
in the general case. So let F = F q be a finite field. Any line of a straight-line program

computing f can be expressed as taking the product of two

F q -linear combinations
of previously computed values. Hence the total number of straight-line programs of
length s is at most q O ( s 2

) polynomials of degree
d on n variables. Hence most n -variate polynomials of degree d require straight-
line progr ams o f length at least (equivalently arithmetic circuits of size at least)
s

) . On the other hand, there are q (

n + d
d

⊣ ⊛ n + d ⊤ .

= ˇ ∈

Hrubes and Yehudayoff [ HY11 ] showed that in fact most n -variate polyn omials of

⊣ ⊛ n + d ⊤ .Nowit
turns out that this is in fact a lower bound on the number of multiplications in any

ˇ

degree d with zero-one coefficients have complexity at least