Optimization, Complexity, Algebra and Invariant Theory

点击翻译按钮获取中文摘要

The research we propose is based on the long-term paradigm: How can we use the inherent algebraic structure of a computational problem to design better algorithms for it? And how can we use the inherent algebraic structure of a lower bound technique to understand its limitations and design better lower bound techniques? Optimization, Algebraic Complexity We aim to develop new algorithmic techniques to solve certain classes of non-convex optimization problems and exponentially large linear programs (moment polytopes). These problems are described by algebraic groups acting linearly on vector spaces. Such non-convex optimization problems arise naturally in diverse areas, such as machine learning (optimal transport distances), quantum information theory (quantum marginal problem), invariant theory (null cone) and functional analysis (Brascamp-Lieb inequalities). The techniques we developed bring out deep connections between optimization, complexity and invariant theory. We have shown vast applications in other areas of science, as the ones mentioned above. Despite the recent developments, many questions remain open. Improvements to our algorithms and analyses could have profound impact in many more areas. Lower bound techniques in algebraic complexity: Algebraic circuits are the main computational model to study the complexity of computing polynomials. Despite remarkable recent progress on lower bounds for restricted classes of circuits, we haven't been able to improve on the (weak) lower bounds obtained in the 80's for general algebraic circuits. We recently proved the first unconditional barrier result (limitations) for a very general class of lower bound techniques which encompass most of the known lower bound techniques in the algebraic setting. We aim to generalize our results to stronger lower bound methods and improve the current barriers. We also aim to develop new techniques to overcome such barriers and obtain stronger algebraic circuit lower bounds. Real Stability, Optimization Semidefinite programming (SDP) and hyperbolic programming (HP) (a generalization of SDP) problems have an inherent algebraic structure: they are optimization problems described by polynomials possessing special positivity properties. SDPs are characterized by determinants of symmetric matrices whereas HPs are characterized by hyperbolic polynomials. SDPs have been more widely used and are better understood than HPs. However, the latter has recently received greater attention due to their natural appearance in problems from diverse areas, ranging from statistical physics, combinatorics and approximate counting algorithms. A fundamental question in the area is whether HPs are indeed more powerful and general than SDPs. This research combines recent developments from real algebraic geometry, combinatorics and in algebraic complexity to bridge structural and computational gaps between two classes of optimization problems.