-
Welcome to ICERM
The Institute for Computational and Experimental Research in Mathematics
-
Welcome to ICERM
The Institute for Computational and Experimental Research in Mathematics
-
Welcome to ICERM
The Institute for Computational and Experimental Research in Mathematics
-
Welcome to ICERM
The Institute for Computational and Experimental Research in Mathematics
This Week at ICERM
Your device timezone is . Do you want to view schedules in or choose a custom timezone?
January 29, 2023
There are no events currently scheduled for January 29th.
January 30, 2023
-
8:30 - 9:30 am ESTCheck In11th Floor Collaborative Space
-
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 mini-course, 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 higher-order 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 mini-course, 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 higher-order 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
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 2-approximation 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 better-than-2 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 2-approximation 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 better-than-2 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
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 n-variables. 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 self-contained 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 n-variables. 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 self-contained introduction to this vibrant and exciting research area.
-
11:40 - 11:45 am ESTGroup Photo11th 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.
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 2-approximation 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 better-than-2 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 2-approximation 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 better-than-2 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 mini-course, 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 higher-order 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 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 mini-course, 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 higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
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 n-variables. 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 self-contained 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 n-variables. 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 self-contained 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
February 4, 2023
There are no events currently scheduled for February 4th.
All event times are listed in ICERM local time in Providence, RI (Eastern Standard Time / UTC-5).
All event times are listed in .
ICERM local time in Providence, RI is Eastern Standard Time (UTC-5). Would you like to switch back to ICERM time or choose a different custom timezone?
Schedule Timezone Updated
Connect with ICERM
GirlsGetMath Program Helps High School Girls Build Confidence in Math and Science
October 12, 2022 - Brown University's news website featured an article about ICERM's 2022 GirlsGetMath program.
Three esteemed Brown scholars spoke at the International Congress of Mathematicians
July 14, 2022 - Kavita Ramanan, Richard Schwartz and Joseph Silverman landed the opportunity, considered a career pinnacle for many, to present at next week’s prestigious ICM conference, an event held once every four years.