Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LINEAR APPROXIMATION:
Reports tagged with Linear approximation:
TR96-030 | 31st March 1996
Meera Sitharam

Approximation from linear spaces and applications to complexity


We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. ... more >>>


TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

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 ... more >>>




ISSN 1433-8092 | Imprint