CAREER: The Geometry of Polynomials in Algorithms and Combinatorics

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.