CAREER: The Geometry of Polynomials in Algorithms and Combinatorics

图形和矩阵是计算机科学中的中心对象。两种最成功的处理和优化它们的范例是谱方法，它研究特征值和特征向量，以及半定规划，它允许在通过对这些特征值施加约束来定义的某些凸集上进行有效的优化。这项提议的目标是研究一种控制本征值的新技术，该技术依赖于多项式几何领域的工具。在最近PI关于Ramanujan展开器图和Kadison-Singer问题的工作中，这种另一种观点被证明是非常强大的，PI相信对它的更全面的理解对于理论计算机科学和数学都将是卓有成效的。在技术层面，PI将专注于多项式几何和计算机科学之间的两个接触点：(A)多项式族的交错方法，这是PI和合作者最近引入的一种新的类似于概率方法的方法，该方法是基于对实根随机多项式的研究。(B)双曲规划，与(A)中出现的多项式密切相关的半定规划的推广。更具体地说，该建议有以下目标：(I)发展对(A)的更系统和更广泛的理解，并用它来解决TCS和应用数学中的中心线性代数和组合问题。(Ii)找到有效的算法来产生由(A)保证存在的有用对象，这些对象目前需要指数时间。(Iii)探索(B)作为组合优化算法原语的力量，特别是作为图划分问题的一种方法，并了解它是否真的比半定规划更强大。提案中概述的问题可能会影响多个领域，如信号处理、量子计算、伪随机性、复杂性理论和算子理论。这门学科对来自数学和计算机科学领域不同背景的学生来说是可以接触到的，所以这个项目旨在为在这些领域工作的研究生和本科生整合研究和教育。

Graphs and matrices are central objects in computer science. Two of the most successful paradigms for manipulating and optimizing over them are spectral methods, which study eigenvalues and eigenvectors, and semidefinite programming, which allows efficient optimization over certain convex sets defined by putting constraints on these eigenvalues. The goal of this proposal is to investigate a new technique for controlling eigenvalues which relies on tools from an area known as the geometry of polynomials. This alternate perspective was shown to be very powerful in recent work of the PI on Ramanujan expander graphs and the Kadison-Singer problem, and the PI believes that a more complete understanding of it will be fruitful both for theoretical computer science and for mathematics.At a technical level, the PI will focus on two points of contact between the geometry of polynomials and computer science: (A) The method of interlacing families of polynomials, a new analogue of the probabilistic method recently introduced by the PI and collaborators, based on studying random polynomials with real roots. (B) Hyperbolic programming, a generalization of semidefinite programming which is intimately related to the polynomials appearing in (A).More specifically, the proposal has the following goals: (i) Develop a more systematic and general understanding of (A) and use this to attack central linear-algebraic and combinatorial problems in TCS and applied math. (ii) Find efficient algorithms for producing the useful objects guaranteed to exist by (A), which currently require exponential time. (iii) Explore the power of (B) as an algorithmic primitive in combinatorial optimization, in particular as an approach to graph partitioning problems, and understand whether it is actually more powerful than semidefinite programming.The problems outlined in the proposal have the potential to impact various fields, such as signal processing, quantum computing, pseudorandomness, complexity theory, and operator theory. The subject is accessible to students of from diverse backgrounds across math and computer science, so this project uses to integrate research and education for both graduate and undergraduate students working between these fields.