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.