期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
