Title: Polynomial systems: Graphical structure, Geometry, and Applications
| Speaker: | Diego Cifuentes |
| Affiliation: | MIT |
| Room: | MC 5501 |
Abstract:
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 talk 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.
The second part of this talk 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 novel guarantees on the quality of this relaxations. 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.