CAREER: The Geometry of Polynomials in Algorithms and Combinatorics

职业：算法和组合学中多项式的几何

• 批准号: 1553751
• 负责人: Nikhil Srivastava
• 金额: $ 41.88万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-02-01 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1553751&HistoricalAwards=false
• 关键词: CAREER; Geometry; Polynomials; Algorithms; Combinatorics

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.

图和矩阵是计算机科学中的中心对象。两个最成功的范例操纵和优化他们的谱方法，研究特征值和特征向量，和半定规划，它允许有效的优化某些凸集上定义的这些特征值的约束。这个建议的目的是调查一种新的技术，用于控制特征值，它依赖于工具，从一个地区被称为几何的多项式。在最近的Ramanujan扩展图和Kadison-Singer问题的研究中，PI证明了这种观点的强大，PI相信对它的更全面的理解将对理论计算机科学和数学都有很大的帮助。在技术层面上，PI将专注于多项式几何和计算机科学之间的两个联系点：（A）多项式族交错法，这是PI及其合作者最近在研究具有真实的根的随机多项式的基础上提出的概率方法的一种新的类似方法。 (B)双曲规划，半定规划的一种推广，它与（A）中出现的多项式密切相关。更具体地说，该提案有以下目标：（i）发展对（A）的更系统和一般的理解，并利用这一点来解决TCS和应用数学中的中心线性代数和组合问题。A），目前需要指数时间。 (iii)探索（B）作为组合优化中的算法原语的能力，特别是作为图划分问题的方法，并了解它是否实际上比半定规划更强大。提案中概述的问题有可能影响各个领域，如信号处理，量子计算，伪随机性，复杂性理论和算子理论。该主题可供来自数学和计算机科学不同背景的学生使用，因此该项目用于整合这些领域之间工作的研究生和本科生的研究和教育。