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

这个项目的目的是理解计算理论中的各种基本问题。它将通过高等研究院的博士后指导计划进行，因此，重点关注的具体主题将随着每年的博士后人数而变化。目前的焦点包括以下内容：-公式的力量。公式是最基本的数学和计算描述机制。了解它们对自然问题的最小长度可以立即捕获对空间要求的限制，以及问题固有的潜在并行性。该奖项将集中在最具挑战性的方向，到目前为止，它抵抗了攻击-证明了公式的局限性。更广泛地说，研究人员将致力于证明其他自然计算模型的局限性，特别是算术计算。-松弛的力量“元算法”：整数规划的线性和半定松弛，是解决(或找到近似解)优化问题最有成效和最强大的技术之一。该奖项将侧重于了解这些技术的局限性。这项工作自然地与理解自然证明系统和搜索算法的自然策略的局限性联系在一起。-窥探编程和学习中最有用的范例之一是将对象封装为黑盒，只允许输入-输出访问。这个实用程序带来了一些限制，如果我们被允许进入黑匣子的内部工作，这些限制有望克服。在科学实验、机器学习和计算复杂性方面，对这种访问进行建模是研究人员计划追求的挑战。计算复杂性是计算机科学的基础核心，在过去的几十年里，它已经证明自己是一个非常深刻和富有成效的问题、思想和技术的源泉。预计研究议程将推动理论计算机科学和相关学科的创新。一些研究领域具有理论之外的潜在影响，特别是机器学习、编码理论、科学发现等。在教育方面，指导计划进一步提高了IAS博士后的质量，使他们成为当今最令人兴奋的科学分支之一的杰出教师、研究生导师、学术领袖和创新者。无论IAS的校友是在学术界还是在行业中追求职业生涯，他们对技术以及对培养新一代本科生和研究生教育的影响都是巨大的。

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.