TR96-049 Authors: Per Enflo, Meera Sitharam

Publication: 26th September 1996 15:18

Downloads: 2424

Keywords:

--

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.