Organizing Committee
Abstract

This workshop will focus on techniques and structures in real algebraic geometry and optimization, including computational tools for semi-algebraic sets, semidefinite programming techniques for polynomial optimization, and applications of these tools to problems in computer vision. Real algebraic geometry provides powerful tools to analyze the behavior of optimization problems, the geometry of feasible sets, and to develop new relaxations for hard non-convex problems. On the other hand, numerical solvers for semidefinite programs have led to new fast algorithms in real algebraic geometry. Algebraic methods over the real numbers are essential for many real-world applications. This workshop aims to explore the cutting edge of techniques in real algebraic geometry and convex optimization as well as applications of these tools to problems in computer vision and other information sciences.

Image for "Real Algebraic Geometry and Optimization"

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, October 15, 2018
TimeEventLocationMaterials
8:30 - 8:55am EDTRegistration - ICERM 121 South Main Street, Providence RI 0290311th Floor Collaborative Space 
8:55 - 9:00am EDTWelcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45am EDTReal Geometry of Matrix Completion - Rainer Sinn, FU Berlin11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTOn Convexity of Polynomials over a Box - Georgina Hall, INSEAD Business School11th Floor Lecture Hall
11:30 - 12:15pm EDTLearning Paths from Signature Tensors - Anna Seigal, UC Berkeley11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:45 - 3:30pm EDTLowerbounds on semidefinite representations of hyperbolic programs - Nikhil Srivastava, UC Berkeley11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTStrict Complementarity in Convex Algebraic Geometry (with a focus on Elliptopes) - Levent Tuncel, University of Waterloo11th Floor Lecture Hall
5:00 - 6:30pm EDTWelcome Reception11th Floor Collaborative Space 
Tuesday, October 16, 2018
TimeEventLocationMaterials
9:00 - 9:45am EDTOn the stability of semidefinite relaxations - Diego Cifuentes, MIT11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTThe Geometry of SDP-Exactness in Quadratic Optimization - Bernd Sturmfels, MPI Leipzig11th Floor Lecture Hall
11:30 - 12:15pm EDTCertificates of polynomial nonnegativity via hyperbolic optimization - James Saunderson, Monash University11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTNegative dependence and Hodge-Riemann relations - Petter Branden, KTH Royal Institute of Technology11th Floor Lecture Hall
3:30 - 5:00pm EDTCoffee/Tea Break and Poster Session11th Floor Collaborative Space 
Wednesday, October 17, 2018
TimeEventLocationMaterials
9:00 - 9:45am EDTFast algebraic solvers for computer vision problems - Zuzana Kúkelová, Czech Technical University11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTCamera Configurations and Viewing Graphs - Matthew Trager, NYU11th Floor Lecture Hall
11:30 - 12:15pm EDTTowards algorithms for analyzing the topology of semi-algebraic sets - Mohab Safey El Din, Sorbonne University11th Floor Lecture Hall
12:30 - 12:40pm EDTGroup Photo11th Floor Lecture Hall 
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTPythagoras numbers of projective varieties - Mauricio Velasco, Universidad de Los Andes11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTConvex sets without representation as spectrahedral shadow - Claus Scheiderer, Universität Konstanz11th Floor Lecture Hall
Thursday, October 18, 2018
TimeEventLocationMaterials
9:00 - 9:45am EDTLarge Graphs and Symmetric Sums of Squares - Annie Raymond, University of Washington11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTThe Tale of One Variety (And Its Family) - Alexander Razborov, University of Chicago11th Floor Lecture Hall
11:30 - 12:15pm EDTLower Bounds on Sums-of-Squares Proof-Size - Albert Atserias, Universitat Politècnica de Catalunya11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTSpectral Algorithms Capture Sum-of-Squares on Average - Tselil Schramm, Harvard University and MIT11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTEfficient Algorithms for Distributional Problems via Sum-of-Squares Proofs - Pravesh Kothari, Institute for Advanced Study and Princeton University11th Floor Lecture Hall
Friday, October 19, 2018
TimeEventLocationMaterials
9:00 - 9:45am EDTNon-commutative Sums of Squares in Quantum Information - Sabine Burgdorf, University of Konstanz11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTThe Paulsen Problem Made Simple - Ankur Moitra, MIT11th Floor Lecture Hall
11:30 - 12:15pm EDTSlack variety of a polytope and its applications - João Gouveia, University of Coimbra11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTPolyhedral approximations of the positive semidefinite cone - Hamza Fawzi, University of Cambridge11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTAn Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization - Timo de Wolff, Technical University Berlin11th Floor Lecture Hall

Associated Semester Workshops

Nonlinear Algebra
Image for "Nonlinear Algebra"
Sep 5 - Dec 7, 2018
Semester Program
Nonlinear Algebra Bootcamp
Image for "Nonlinear Algebra Bootcamp"
Sep 5 - 12, 2018
Semester Workshop
Core Computational Methods
Image for "Core Computational Methods"
Sep 17 - 21, 2018
Semester Workshop
Nonlinear Algebra in Applications
Image for "Nonlinear Algebra in Applications"
Nov 12 - 16, 2018
Semester Workshop

Lecture Videos

An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization

Timo de Wolff
Technical University Berlin
October 19, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Polyhedral approximations of the positive semidefinite cone

Timo de Wolff
Technical University Berlin
October 19, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Slack variety of a polytope and its applications

João Gouveia
University of Coimbra
October 19, 2018
Real Algebraic Geometry and Optimization
Play     Abstract     Slides

The Paulsen Problem Made Simple

Ankur Moitra
MIT
October 19, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Polynomial Optimization in Quantum Information Theory

Sabine Burgdorf
University of Konstanz
October 19, 2018
Real Algebraic Geometry and Optimization
Play     Abstract     Slides

Efficient Algorithms for Distributional Problems via Sum-of-Squares Proofs

Pravesh Kothari
Institute for Advanced Study and Princeton University
October 18, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Spectral Algorithms Capture Sum-of-Squares on Average

Tselil Schramm
Harvard/MIT
October 18, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Lower Bounds on Sums-of-Squares Proof-Size

Albert Atserias
Universitat Politècnica de Catalunya
October 18, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

The Tale of One Variety (And Its Family)

Alexander Razborov
University of Chicago
October 18, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Large Graphs and Symmetric Sums of Squares

Annie Raymond
University of Massachusetts, Amherst
October 18, 2018
Real Algebraic Geometry and Optimization
Play     Abstract     Slides

Convex sets without representation as spectrahedral shadow

Claus Scheiderer
Universität Konstanz
October 17, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Pythagoras numbers of projective varieties

Mauricio Velasco
Universidad de Los Andes
October 17, 2018
Real Algebraic Geometry and Optimization
Play     Abstract     Slides

Camera Configurations and Viewing Graphs

Matthew Trager
NYU
October 17, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Fast algebraic solvers for computer vision problems

Zuzana Kúkelová
Czech Technical University
October 17, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Negative dependence and Hodge-Riemann relations

Petter Branden
KTH Royal Institute of Technology
October 16, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Certificates of polynomial nonnegativity via hyperbolic optimization

James Saunderson
Monash University
October 16, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

The Geometry of SDP-Exactness in Quadratic Optimization

Bernd Sturmfels
MPI Leipzig
October 16, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

On the stability of semidefinite relaxations

Diego Cifuentes
MIT
October 16, 2018
Real Algebraic Geometry and Optimization
Play     Abstract     Slides

Strict Complementarity in Convex Algebraic Geometry (with a focus on Elliptopes)

Levent Tuncel
University of Waterloo
October 15, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Lowerbounds on semidefinite representations of hyperbolic programs

Nikhil Srivastava
UC Berkeley
October 15, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

Learning Paths from Signature Tensors

Anna Seigal
UC Berkeley
October 15, 2018
Real Algebraic Geometry and Optimization
Play     Abstract

On Convexity of Polynomials over a Box

Georgina Hall
INSEAD Business School
October 15, 2018
Real Algebraic Geometry and Optimization
Play     Abstract     Slides

Real Geometry of Matrix Completion

Rainer Sinn
FU Berlin
October 15, 2018
Real Algebraic Geometry and Optimization
Play     Abstract