This project examines problems in circuit complexity, using classical analytic methods. The project is centered around three basic questions, the first and last of which are specifically geared towards basic, long-unresolved issues that have hindered progress in the area. (1) Do simple operations (such as shifts, or products) on hard functions preserve hardness? (3) In what ways can hardness be used for learning functions in a complexity class? (2) What are the analytic properties that are common to constant depth circuits with various sets of symmetric gates? Already partial answers have yielded the following: (a) a non-trivial, complexity bounds involving constant depth circuits and more significantly, the analytic patterns underlying such bounds; (b) general methods for using hard functions to obtain large classes of pseudorandom generators and training sets for learning; and (c) conversion of lower bounds on circuit complexity into upper bounds on the complexity of learning, and vice versa. The analytic techniques used, are partly multivariate generalizations of univariate approximation methods, partly from coding theory and partly from spectral analysis. The techniques developed are of independent interest to approximation theorists, and solve, in particular, a number of problems involving general Boolean functions, and combinatorics over the multidimensional unit-cube.
