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.