RIA: Proving Circuit Complexity Bounds Using Classical Analytic Methods

RIA：使用经典分析方法证明电路复杂性界限

基本信息

批准号：
9409809
负责人：
Meera Sitharam
金额：
$ 9.32万
依托单位：
Kent State University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
1994
资助国家：
美国
起止时间：
1994-09-01 至 1998-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409809&HistoricalAwards=false
关键词：
RIA Proving Circuit Complexity Bounds

项目摘要

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.

该项目使用经典的分析方法研究了电路复杂性的问题。该项目围绕三个基本问题，第一个也是最后一个问题专门针对基本的，长期解决的问题，阻碍了该地区的进展。（1）对硬功能的简单操作（例如班次或产品）是否可以保留硬度？（3）在复杂性类别中，以什么方式可以将硬度用于学习功能？（2）具有各种对称门的恒定深度电路的共同分析性能是什么？已经部分答案产生了以下内容：（a）涉及恒定深度电路的非平凡，复杂性界限，更重要的是，这种界限的分析模式；（b）使用硬功能获得大量伪随机生成器和学习训练集的一般方法；（c）在学习复杂性上，电路复杂性上的下限转换为上限，反之亦然。所使用的分析技术是单变量近似方法的部分多变量概括，部分来自编码理论，部分来自光谱分析。所开发的技术对近似理论家具有独立的兴趣，特别是解决了许多涉及一般布尔函数的问题，以及在多维单位立方体上的组合。