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.