Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-030 | 31st March 1996 00:00

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. This isolates the analytic
content of these problems from their combinatorial content
and clarifies the close relationship between the analytic
structure of questions.

(1) We give several, general
results that characterize approximability from
spaces of functions and hence also represent general analytic
methods for showing non approximability.

(2) We point out that crucial portions
of a significant number
of the known complexity-related results
can be given shorter and cleaner proofs using these
general theorems: this
clarifies their common analytic structure. We however
provide only a few of the alternative proofs.

(3) We give several new complexity-related
applications, including circuit complexity
lower bounds, and results concerning pseudorandomness,
learning, and combinatorics of Boolean functions.

(4) Finally, we suggest natural and promising
directions for further investigation.

ISSN 1433-8092 | Imprint