UC Berkeley

We explore connections between hyperbolic polynomials and computer science problems involving optimization and counting. Specifically we investigate the following diverse set of topics, all of which are connected through the modern study of hyperbolic polynomials:

\textbf{Independent Sets}. To count independent sets of graphs, we study a multivariate generating polynomial for independence sets and prove generalizations of results of Chudnovsky and Seymour relating to real-rootedness of the polynomials.

\textbf{Differential Operators}.

In the study of spectral graph theory and spectral discrepancy theory, the classical additive convolution is used to study the effect differential operators have on the roots of real rooted polynomials. We refine some existing tools for studying the movement of max root under differential operators and establish some conjectures for controlling the inner roots.

\textbf{Finite Difference Operators}. Lamprecht studies a

$q-$extension of the classical multiplicative convolution which abstracts classical results. We extend the study of such generalizations by considering a finite-mesh preserving generalization of the classical additive convolution.

\textbf{Membership Algorithm}. We initiate a conversation around developing algorithms to solve fundamental tasks in this field by establishing an exact arithmetic polynomial time algorithm to determine whether a given bivariate polynomial is real-stable. By the characterization theorem of Br{\"a}nd{ e}n and Borcea this is equivalent to an algorithm for testing whether a given linear transformation $T: \R_d[x] \to \R[x]$ sends real rooted polynomials to real rooted polynomials.

\textbf{Convex Optimization Complexity}. Given a hyperbolic polynomial one can do convex optimization over its hyperbolicity cone. The exact algorithmic relationship between semidefinite programming and hyperbolic programming is an open question. In an attempt to further motivate complexity questions between these two primitives we give a random family of polynomials which require exponentially sized approximate semidefinite representations for their hyperbolicity cones.