Information Technology Reference
In-Depth Information
circuit computing a random polynomial. Lovett [
Lov11
] complements this nicely by
giving a matching upper bound. Specifically, it was shown in [
Lov11
] that for any
polynomial
f
of degree
d
on
n
variables there exists a circuit computing
f
having
at most
⊣
⊛
n
+
d
⊤
O
(
1
)
multiplications.
·
(
nd
)
5.3 Weak Lower Bounds for General Circuits and Formulas
Despite several attempts by various researchers to prove lower bounds for arithmetic
circuits or formulas, we only have very mild lower bounds for general circuits or
formulas thus far. In this section, we shall look at the two modest lower bounds for
general circuits and formulas.
5.3.1 Lower Bounds for General Circuits
The only super-linear lower bound we currently know for general arithmetic circuits
is the following result of Baur and Strassen [
BS83
].
x
d
+
1
1
Theorem 2
[
BS83
]
Any fan-in two circuit that computes the polynomial f
=
+
x
d
+
1
n
···+
has size
ˇ(
n
log
d
)
.
5.3.1.1 An Exploitable Weakness
Each gate of the circuit
computes a local operation on the two children. To formalize
this, define a new variable
y
g
ʲ
for every gate
g
∗
ʲ
. Further, for every gate
g
define
a quadratic equation
Q
g
as
⊝
y
g
−
(
y
g
1
+
y
g
2
)
if
g
=
g
1
+
g
2
Q
g
=
y
g
−
(
y
g
1
·
y
g
2
)
if
g
=
g
1
·
g
2
.
Further if
y
o
corresponds to the output gate, then the system of equations
⊞
Q
g
=
:
g
∗
ʲ
⊠
∃ {
0
y
o
=
1
}
completely characterize the computations of
that results in an output of 1.
The same can also be extended for
multi-output
circuits that compute several
polynomials simultaneously. In such cases, the set of equations
⊞
Q
g
=
ʲ
:
g
∗
ʲ
⊠
∃
⊞
y
o
i
n
⊠
=
:
=
,...,
0
1
i
1
