RIA: Proving Circuit Complexity Bounds Using Classical Analytic Methods

这个项目使用经典的分析方法来研究电路复杂性中的问题。该项目围绕三个基本问题展开，第一个也是最后一个问题专门针对阻碍该领域进展的长期悬而未决的基本问题。(1)对硬函数的简单运算(如移位或乘积)能保持硬度吗？(3)在复杂类中，硬度可以用什么方式来学习函数？(2)具有各种对称门的恒定深度电路的共同分析性质是什么？已经产生了以下部分答案：(A)涉及恒定深度电路的非平凡的复杂性界限，更重要的是，这些界限背后的分析模式；(B)使用硬函数获得用于学习的大类伪随机生成器和训练集的一般方法；以及(C)将电路复杂性的下界转换为学习的复杂性的上界，反之亦然。所使用的分析技术，部分是单变量近似方法的多变量推广，部分来自编码理论，部分来自频谱分析。所开发的技术是逼近理论家独立感兴趣的，特别是解决了涉及一般布尔函数和多维单位立方上的组合学的一些问题。

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.