Thesis Defense: Polynomial Systems: Graphical Structure, Geometry, and Applications

Various problems in areas such as robotics, power systems, computer vision, cryptography, and chemical reaction networks, can be modeled by systems of polynomial equations, and in many cases the resulting systems have a simple sparsity structure. In the first part of this thesis we represent this sparsity structure with a graph, and study the algorithmic and complexity consequences of this graphical abstraction. In particular, we derive novel algorithms to solve polynomial systems. These methods outperform existing techniques by orders of magnitude in certain applications from algebraic statistics and vector addition systems. We also investigate the effect of graphical structure in computing quantities from convex geometry such as matrix permanents and mixed discriminants.

The second part of this thesis focuses on the problem of minimizing a polynomial function subject to polynomial equality constraints. This problem captures many important applications, including Max-Cut, tensor low rank approximation, the triangulation problem, and rotation synchronization. Although these problems are nonconvex, tractable semidefinite programming (SDP) relaxations have been proposed. We show that the geometry of the underlying algebraic set may enable more efficient (smaller) relaxations, and also improved guarantees on the quality of the relaxation. In particular, we prove that estimation problems such as camera triangulation, rank one tensor approximation and rotation synchronization can be solved exactly by SDP relaxations in the low noise regime.