Approximation from linear spaces and applications to complexity
Meera Sitharam · 1996
. We develop an analytic framework based on linear approximation and duality and point out how a number of apparently diverse 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 results that convert a statement of nonapproximability from spaces of functions to statements of approximability. We point how that crucial portions of a significant number of the known complexity-related results can be unified and given shorter and cleaner proofs using these general theorems. (2) We give several new complexity-related applications, including circuit complexity lower bounds, and results concerning pseudorandomness, learning, and combinator...