期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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
functions.
In addition, we obtain new and
general complexity upper bounds by exploring approximation
from Boolean bases and the transitivity of approximability
relationships.
--
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
indicates
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
model.
--
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.
