Organizing Committee
 Jesús De Loera
University of California, Davis  Antoine Deza
McMaster University  Marcia Fampa
Federal University of Rio de Janeiro  Volker Kaibel
OttovonGuericke Universität Magdeburg  Jon Lee
University of Michigan  Laura Sanità
Bocconi University of Milan
Abstract
Discrete optimization is a vibrant area of computational mathematics devoted to efficiently finding optimal solutions among a finite or countable set of possible feasible solutions.
This Bootcamp will be the opening event of the semester and it aims to attract young researchers to this topic.The four mini courses, presented by four speakers known for highquality exposition, will cover various subjects such as new advances in approximation algorithms, mixed integer nonlinear programming, algebraic techniques in optimization and applications to social sciences. The event provides a taste of the many methods and hot topics to be discussed during the semester. The event will also include a poster session to allow graduate students to present their work and other community building activities.
Confirmed Speakers & Participants
Talks will be presented virtually or inperson as indicated in the schedule below.
 Speaker
 Poster Presenter
 Attendee
 Virtual Attendee

Hessa AlThani
University of Michigan

Félix Almendra Hernández
UC Davis

Nicholas Arosemena
Brown University

Nancy Arratia Martinez
Universidad de las Américas Puebla

Ishan Bansal
Cornell University

Alex Black
UC Davis

Teressa Chambers
Brown University

Effrosyni Chasioti
Kent State University

Zhongzhu Chen
University of Michigan

Francisco Criado Gallart
CUNEF Universidad

Maria Dascalu
University of Massachusetts Amherst

Jesús De Loera
University of California, Davis

Yuri Faenza
Columbia University

Marcia Fampa
Federal University of Rio de Janeiro

Allison Fitisone
University of Kentucky

Rohan Ghuge
University of Michigan

Weston Grewe
University of Colorado Denver

Chengyue He
Columbia University

Dylan HyattDenesik
Eindhoven University of Technology

Sean Kafer
University of Waterloo

Lennart Kauther
RWTH Aachen University

Aida Khajavirad
Lehigh University

Sammy Khalife
Johns Hopkins University

Shubhang Kulkarni
University of Illinois, UrbanaChampaign

Jon Lee
University of Michigan

Juan Carlos Martinez Mori
Cornell University

Chiara Meroni
ICERM

Jared Miller
Northeastern University

Bento Natura
Georgia Tech

Gabriel Oliveira da Ponte
Federal University of Rio de Janeiro

Yuchong Pan
MIT

Ethan Partida
Brown

Rodolfo Quintero Ospina
Lehigh University

Laura Sanità
Bocconi University of Milan

Nimita Shinde
IITBMonash Research Academy

Vera Traub
University of Bonn

Mauricio Velasco
Universidad de Los Andes

Lucy Verberk
Eindhoven University of Technology

Aapeli Vuorinen
Columbia University

Fei Wang
University of Waterloo

Chengyang Wang
UC Davis

William Wesley
University of California Davis

Chao Xu
University of Electronic Science and Technology of China

Luze Xu
University of California, Davis

Shixuan Zhang
Brown University

Yuan Zhou
University of Kentucky
Workshop Schedule
Monday, January 30, 2023

9:30  9:50 am ESTCheck In11th Floor Collaborative Space

9:50  10:00 am ESTWelcome11th Floor Lecture Hall
 Brendan Hassett, ICERM/Brown University

10:00  11:00 am ESTMatching Theory and School ChoiceSeminar  11th Floor Lecture Hall
 Speaker
 Yuri Faenza, Columbia University
 Session Chair
 Jon Lee, University of Michigan
Abstract
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.

11:00  11:30 am ESTCoffee Break11th Floor Collaborative Space

11:30 am  12:30 pm ESTMatching Theory and School ChoiceSeminar  11th Floor Lecture Hall
 Speaker
 Yuri Faenza, Columbia University
 Session Chair
 Jon Lee, University of Michigan
Abstract
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.

12:30  2:30 pm ESTLunch/Free Time

2:30  3:30 pm ESTBinary polynomial optimization: theory, algorithms, and applicationsSeminar  11th Floor Lecture Hall
 Speaker
 Aida Khajavirad, Lehigh University
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In this minicourse, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higherorder Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.

3:30  4:00 pm ESTCoffee Break11th Floor Collaborative Space

4:00  5:00 pm ESTBinary polynomial optimization: theory, algorithms, and applicationsSeminar  11th Floor Lecture Hall
 Speaker
 Aida Khajavirad, Lehigh University
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In this minicourse, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higherorder Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.

5:00  6:30 pm ESTReception11th Floor Collaborative Space
Tuesday, January 31, 2023

9:00  10:00 am ESTApproximation Algorithms for Network Design ProblemsSeminar  11th Floor Lecture Hall
 Speaker
 Vera Traub, University of Bonn
 Session Chair
 Laura Sanità, Bocconi University of Milan
Abstract
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first betterthan2 approximation algorithm for Weighted Connectivity Augmentation.

10:00  10:30 am ESTCoffee Break11th Floor Collaborative Space

10:30  11:30 am ESTApproximation Algorithms for Network Design ProblemsSeminar  11th Floor Lecture Hall
 Speaker
 Vera Traub, University of Bonn
 Session Chair
 Laura Sanità, Bocconi University of Milan
Abstract
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first betterthan2 approximation algorithm for Weighted Connectivity Augmentation.

11:45 am  1:00 pm ESTProblem Session11th Floor Lecture Hall

1:00  3:00 pm ESTLunch/Free Time

3:00  5:00 pm EST
Wednesday, February 1, 2023

9:00  10:00 am ESTPolynomial optimization on finite setsSeminar  11th Floor Lecture Hall
 Speaker
 Mauricio Velasco, Universidad de Los Andes
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in nvariables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a selfcontained introduction to this vibrant and exciting research area.

10:00  10:30 am ESTCoffee Break11th Floor Collaborative Space

10:30  11:30 am ESTPolynomial optimization on finite setsSeminar  11th Floor Lecture Hall
 Speaker
 Mauricio Velasco, Universidad de Los Andes
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in nvariables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a selfcontained introduction to this vibrant and exciting research area.

11:40  11:45 am ESTGroup Photo (Immediately After Talk)11th Floor Lecture Hall

11:45 am  2:00 pm ESTLunch/Free Time

2:00  3:00 pm ESTMatching Theory and School ChoiceSeminar  11th Floor Lecture Hall
 Speaker
 Yuri Faenza, Columbia University
 Session Chair
 Jon Lee, University of Michigan
Abstract
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.

3:00  3:30 pm ESTCoffee Break11th Floor Collaborative Space

3:30  4:30 pm ESTMatching Theory and School ChoiceSeminar  11th Floor Lecture Hall
 Speaker
 Yuri Faenza, Columbia University
 Session Chair
 Jon Lee, University of Michigan
Abstract
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
Thursday, February 2, 2023

9:00  10:00 am ESTApproximation Algorithms for Network Design ProblemsSeminar  11th Floor Lecture Hall
 Speaker
 Vera Traub, University of Bonn
 Session Chair
 Laura Sanità, Bocconi University of Milan
Abstract
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first betterthan2 approximation algorithm for Weighted Connectivity Augmentation.

10:00  10:30 am ESTCoffee Break11th Floor Collaborative Space

10:30  11:30 am ESTApproximation Algorithms for Network Design ProblemsSeminar  11th Floor Lecture Hall
 Speaker
 Vera Traub, University of Bonn
 Session Chair
 Laura Sanità, Bocconi University of Milan
Abstract
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first betterthan2 approximation algorithm for Weighted Connectivity Augmentation.

11:30 am  1:30 pm ESTLunch/Free Time

1:30  2:30 pm ESTBinary polynomial optimization: theory, algorithms, and applicationsSeminar  11th Floor Lecture Hall
 Speaker
 Aida Khajavirad, Lehigh University
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In this minicourse, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higherorder Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.

2:30  3:30 pm ESTCoffee Break11th Floor Collaborative Space

3:30  4:30 pm ESTRankone Boolean tensor factorization and the multilinear polytopeSeminar  11th Floor Lecture Hall
 Speaker
 Aida Khajavirad, Lehigh University
 Session Chair
 Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In this minicourse, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higherorder Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
Friday, February 3, 2023

10:00  11:00 am ESTPolynomial optimization on finite setsSeminar  11th Floor Lecture Hall
 Speaker
 Mauricio Velasco, Universidad de Los Andes
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in nvariables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a selfcontained introduction to this vibrant and exciting research area.

11:00  11:30 am ESTCoffee Break11th Floor Collaborative Space

11:30 am  12:30 pm ESTPolynomial optimization on finite setsSeminar  11th Floor Lecture Hall
 Speaker
 Mauricio Velasco, Universidad de Los Andes
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in nvariables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a selfcontained introduction to this vibrant and exciting research area.

12:30  2:30 pm ESTLunch/Free Time

3:30  4:00 pm ESTCoffee Break11th Floor Collaborative Space
All event times are listed in ICERM local time in Providence, RI (Eastern Daylight Time / UTC4).
All event times are listed in .
ICERM local time in Providence, RI is Eastern Daylight Time (UTC4). Would you like to switch back to ICERM time or choose a different custom timezone?
MiniCourses
Binary polynomial optimization: theory, algorithms, and applications
Aida Khajavirad (Lehigh University)
In this minicourse, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments.
Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higherorder Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
Matching Theory and School Choice
Yuri Faenza (Columbia University)
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
Approximation Algorithms for Network Design Problems
Vera Traub (ETH Zurich)
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first betterthan2 approximation algorithm for Weighted Connectivity Augmentation.
Polynomial optimization on finite sets
Mauricio Velasco (U. Andes Colombia)
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in nvariables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms.
In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss:
 How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity?
 If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization?
 Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$
Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems.
The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a selfcontained introduction to this vibrant and exciting research area.