Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-049 | 9th September 1996 00:00

Stable basis families and complexity lower bounds



Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable basis families, in particular, include orthonormal basis families.

To do this, we define and distinguish between
several related notions of approximation,
and give general methods of proving nonapproximability,
(both directly and by using the transitive nature of
approximation). These give complexity lower bounds:
we point out
how several of the methods commonly used for proving
threshold and communication complexity
lower bounds including the ``discriminator/correlation/ discrepancy
method,'' the ``communication complexity'' method, and
the ``variation rank/geometric method,'' reduce to three
closely related notions of nonapproximability
that depend on
estimates on the scalar products
between functions. Therefore, we give general techniques for obtaining
these estimates and in particular, we obtain estimates for specific
In addition, we obtain new and
general complexity upper bounds by exploring approximation
from Boolean bases and the transitivity of approximability

We give examples of
natural Boolean basis families that are stable,
give an alternative proof, using scalar product estimates, of an
old lower bound of Krause and Pudla'k in their STOC 94 paper
for the weighted threshold of
parities, and moreover,
for certain unstable bases,
we provide a method of adapting
scalar product estimates to give lower bounds.

One of the examples of stable basis families
a direct method -using scalar product estimates -
for proving lower bounds
for an algebraic circuit model, which is related
to the more standard, arithmetic circuit,
and the algebraic, linear decision tree

We give a method for constructing unstable
bases, and show that
even simple families of threshold functions,
are unstable, thereby indicating a possible reason why
lower bounds for
weighted thresholds of thresholds are proving
so difficult.

ISSN 1433-8092 | Imprint