Grant: Discovery Grants Program - Individual
University of Waterloo
$40,000.00
Optimization, Complexity, Algebra and Invariant Theory
FY 2022-23
Summary
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 & Invariant Theory: 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 & Algebraic Complexity: 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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2020-04599
Name nom
Mendes de Oliveira, Rafael
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2020
Award amount
40000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:3
Partie
1
Nb partie
5
Application title
Optimization, Complexity, Algebra and Invariant Theory
Application summary
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 & Invariant Theory: 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 & Algebraic Complexity: 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.