Information Technology Reference
In-Depth Information
5.4 “Natural” Proof Strategies
The lower bounds presented in Sect.
5.3
proceeded by first identifying a
weakness
of the model, and exploiting it in an explicit manner. More concretely, Sect.
5.3.2
presents a promising strategy that could be adopted to prove lower bounds for various
models of arithmetic circuits. The crux of the lower bound was the construction of a
good map
[
Kal
]
was useful
to show a lower bound in the sense that any
f
computable by a
small
formula had
small
that assigned a number to every polynomial. The map
[
Kal
]
(
. In fact, all subsequent lower bounds in arithmetic circuit complexity
have more or less followed a similar template of a “natural proof”. More concretely,
all the subsequent lower bounds we shall see would essentially follow the outlined
plan.
f
)
Step 1 (normal forms)
For every circuit in the circuit class
C
of interest, express the poly-
nomial computed as a
small sum of simple building blocks
.
circuit is a
small
sum of
products of linear polyno-
mials
which are the building blocks here. In this case, the circuit model naturally
admits such a representation but we shall see other examples with very different
representations as sum of building blocks.
For example, every
Step 2 (complexity measure)
Construct amap
:
F
[
x
1
,...,
x
n
]∩
Z
ↆ
0
that is
sub-additive
i.e.,
(
f
1
+
f
2
)
≥
(
f
1
)
+
(
f
2
)
.
(
)
is the rank of a large matrix whose entries are linear functions
in the coefficients of
f
. In such cases, we immediately get that
In most cases,
f
is sub-additive.
The strength of the choice of
is determined by the next step.
Step 3 (potential usefulness)
Show that if
B
is a
simple building block
,then
(
B
)
is
small
.
Further, check if
(
f
)
for a
random polynomial f
is large (potentially).
This would suggest that if any
f
with large
(
f
)
is to be written as a sum of
B
1
+···+
B
s
, then sub-additivity and the fact that
(
B
i
)
is small for each
i
and
(
is large immediately imply that
s
must be large. This implies that the complexity
measure
f
)
does indeed have a potential to prove a lower bound for the class. The
next step is just to replace the
random polynomial
by an explicit polynomial.
Step 4 (explicit lower bound)
Find an explicit polynomial
f
for which
(
f
)
is large.
These are usually the steps taken in almost all the known arithmetic circuit lower
bound proofs. The main ingenuity lies in constructing a useful complexity measure,
which is really to design
so that it is small on the
building blocks
.
Of course, there could potentially be lower bound proofs that do not follow the
roadmap outlined. For instance, it could be possible that
is not small for a random
polynomial, but specifically tailored in a way to make
large for the
Perm
n
.Or
perhaps
need not even be sub-additive and maybe there is a very different way
to argue that all polynomial in the circuit class have small
. However, this has
been the roadmap for almost all lower bounds so far (barring very few exceptions).
