AF: Large: Theory of Computation - Pushing the State-of-the-Art

AF：大：计算理论 - 推动最先进的技术

• 批准号: 1412958
• 负责人: Avi Wigderson
• 金额: $ 200万
• 依托单位: Institute For Advanced Study
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1412958&HistoricalAwards=false
• 关键词: AF; Large; Theory; Computation; Pushing

This project is aimed at understanding a variety of fundamental questions in the theory of computation. It will be carried out via the postdoctoral mentoring program at the Institute for Advanced Study, and as such the specific topics of focus will evolve with the postdocs present each year. Current foci include, among others, the following:- The power of formulas. Formulas is the most basic mathematical and computational descriptive mechanisms. Understanding their minimal length for natural problems captures at once limitation on the space requirements, as well as the potential parallelism inherent in the problem. The award will focus on the most challenging direction, which has so far resisted attack - proving limitation of formulas. More generally, the researchers will pursue proving limitations of other natural computational models, especially arithmetic computation.- The power of relaxationsThe "meta-algorithms": Linear and semi-definite relaxations of integer programs, are among the most fruitful and powerful techniques for solving (or finding approximate solutions) to optimization problems. The award will focus on understanding the limits of these techniques. This work ties in naturally to understanding the limitations of natural proof systems and of natural strategies for search algorithms.- Peeking inside the "black-box"One of the most useful paradigms in programming and learning is the encapsulation of objects as black-boxes, to which only input-output access is allowed. With this utility come limitations which can hopefully overcome if we are allowed some access into the internal workings of the black box. Modeling such access, in scientific experiments, machine learning and computational complexity is a challenge the researchers plan to pursue.Computational complexity, a foundational core of computer science, has proved itself a remarkably deep and fruitful fountain of problems, ideas and techniques over the past decades. The research agenda is expected to be a driver of innovation in Theoretical Computer Science and related disciplines. Some of the areas of study have potential implications outside theory, especially machine learning, coding theory, scientific discovery and more. On the educational side, the mentoring program furthers the quality of IAS postdocs to serve as outstanding teachers, graduate advisors and academic leaders and innovators in one of the most exciting branches of science today. Whether IAS alumni pursue a career in academia or industry their impact on technology and on the training of new generations undergraduate and graduate education is immense.

该项目旨在了解计算理论中的各种基本问题。 它将通过高级研究研究所的博士后指导计划进行，因此，专注的特定主题将随着每年存在的博士后的发展而发展。当前的焦点包括以下内容： - 公式的力量。公式是最基本的数学和计算描述机制。了解它们最小的自然问题长度立即捕获了空间需求以及问题固有的潜在并行性。该奖项将集中在最具挑战性的方向上，到目前为止，该方向抵制了攻击 - 证明了公式的限制。更一般而言，研究人员将追求其他自然计算模型的证明局限性，尤其是算术计算。-放松的力量“元算法”：整数程序的线性和半明确放松，是最有成果和强大的技术之一，用于解决（或寻找近似解决方案）到优化问题。该奖项将集中于理解这些技术的局限性。这项工作与理解自然证明系统的局限性以及搜索算法的自然策略的局限性自然相关。-在编程和学习中最有用的范式之一内浏览“黑盒”中最有用的范式之一是将物体封装为黑盒，仅允许输入输入输入访问。 随着该公用事业的限制，如果我们允许我们进入黑匣子的内部运作，可以有望克服。 在科学实验，机器学习和计算复杂性中对这种访问进行建模是研究人员计划追求计算机科学的基础核心的挑战。 预计该研究议程将是理论计算机科学和相关学科创新的驱动力。一些研究领域在理论之外具有潜在的影响，尤其是机器学习，编码理论，科学发现等。在教育方面，指导计划进一步提高了IAS博士后的质量，成为当今最令人兴奋的科学分支之一，成为杰出的教师，研究生顾问，学术领导者和创新者。 无论是IAS校友从事学术界还是行业的职业，他们对技术的影响以及对新一代本科和研究生教育的培训都是巨大的。

项目成果

Automating cutting planes is NP-hard

自动化切割平面是 NP 困难的

• DOI: 10.1145/3357713.3384248
• 发表时间: 2020
• 期刊: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Göös, M;Koroth, S;Mertz, I;Pitassi, T.
• 通讯作者: Pitassi, T.

Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings

不变环生成元的代数复杂性、GCT 和硬度搜索问题

• 发表时间: 2020
• 期刊: Computational Complexity Conference (CCC
• 作者: Garg, A;Ikenmeyer, C;Makam, V;Oliveira, R;Walter, M;Wigderson, A.
• 通讯作者: Wigderson, A.

Geometric rank of tensors and subrank of matrix multiplication

张量的几何秩和矩阵乘法的子秩

• 发表时间: 2020
• 期刊: Electronic colloquium on computational complexity
• 作者: Kopparty, S;Moshkovitz, G;Zuiddam, J.
• 通讯作者: Zuiddam, J.

AND testing and robust judgement aggregation

AND 测试和稳健的判断聚合

• DOI: 10.1145/3357713.3384254
• 发表时间: 2020
• 期刊: STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Filmus, Y;Lifshitz, N;Minzer, D;Mossel, E.
• 通讯作者: Mossel, E.