This Week at ICERM
Your device timezone is . Do you want to view schedules in or choose a custom timezone?
March 19, 2023
There are no events currently scheduled for March 19th.
March 20, 2023
-
3:30 - 4:00 pm EDTCoffee Break11th Floor Collaborative Space
March 21, 2023
-
9:00 - 10:00 am EDTProfessional Development: Hiring ProcessProfessional Development - 11th Floor Lecture Hall
-
10:30 - 11:15 am EDTMemory-efficient approximation algorithm for SDPs and its application to Max-Cut, Max-k-Cut, and Correlation ClusteringSeminar - 11th Floor Lecture Hall
- Nimita Shinde, IITB-Monash Research Academy
Abstract
Semidefinite programs (SDPs) are a special class of convex optimization problems that have a wide range of applications in areas such as control theory, statistical modeling, correlation clustering, community detection, angular synchronization, and combinatorial optimization. We discuss three fundamental graph partitioning problems Max-Cut, Max-k-Cut, and the Max-Agree variant of correlation clustering. Given a graph G = (V, E), Max-k-Cut aims to divide the nodes into k partitions such that the weight of the edges crossing the partitions is maximized. Max-Cut is a special case of Max-k-Cut with k = 2. While Max-Agree requires additional information about the ‘similarity’ or ‘dissimilarity’ of each pair of nodes (i, j) in E, and seeks to cluster the nodes of the graph such that the sum of the ‘similar’ edges within the cluster and ‘dissimilar’ edges across the clusters is maximized. For large-scale instances of problems, the memory required to solve SDPs becomes a key computational bottleneck. We review a Gaussian sampling-based technique that replaces the decision variable of SDP with a zero-mean Gaussian random vector whose covariance is equal to the value of the decision variable. This leads to a Frank-Wolfe based algorithmic framework that tracks the random vectors instead of the matrix iterates. We then apply this technique to the three combinatorial optimization problems, Max-Cut, Max-k-Cut, and Max-Agree. We show that the proposed algorithmic framework uses O(|V | + |E|) memory and generates an approximate solution to the input problem in polynomial time that nearly achieves the best existing approximation guarantees.
-
11:15 am - 12:00 pm EDTBurer-Monteiro low-rank optimization for sum-of-square certification11th Floor Lecture Hall
- Shixuan Zhang, Brown University
Abstract
To certify a sum of $k$ squares on a real projective variety, one can minimize the distance of the sum of squares of $k$ linear forms from it in the space of quadrics. When $k$ is smaller than the dimension of linear forms, the certification problem can be applied in low-rank semidefinite relaxation of polynomial optimization, dual to the Burer-Monteiro method. In this talk, we give some preliminary results on the existence of spurious stationary points in this certification problem by explicit examples and some further study on their structure when the varieties have minimal degrees. For general varieties, we propose algorithmic remedies that guarantee the convergence to global minima.
-
3:30 - 4:00 pm EDTCoffee Break11th Floor Collaborative Space
March 22, 2023
-
3:30 - 4:00 pm EDTMentoring Coffee / TeaCoffee Break - 11th Floor Collaborative Space
March 23, 2023
-
2:00 - 2:30 pm EDTFourier on convex compact bodies: Siegel meets MinkowskiPost Doc/Graduate Student Seminar - 11th Floor Lecture Hall
- Sammy Khalife, Johns Hopkins University
Abstract
In 1889, Minkowski provided a sufficient and necessary condition for a symmetric convex body K in R^d to contain an integral point in its interior, given by Vol(K) > 2^{d}. After introducing the relevant facts in Fourier Analysis, I will discuss how one can use them to get a stronger statement expressing the gap between Vol(K) and 2^{d} in general. These results can be easily extended to intersection with Lattices and to K being compact. An application will be to deduce an original characterization of the extremal bodies, i.e. convex symmetric bodies such that Vol(K)=2^d. They correspond to the bodies which, when scaled by half, tile R^d after translations by the integral points.
-
2:30 - 3:00 pm EDTPPAD hardness – the complexity of Nash equilibriumPost Doc/Graduate Student Seminar - 11th Floor Lecture Hall
- Chengyue He, Columbia University
Abstract
PPAD is a class of search problems where the solution is shown to exist by a parity argument. Whether a PPAD-complete problem admits a polytime algorithm raises significant attention in the algorithmic game theory community. We will present a brief introduction to this class by both discrete (Sperner’s lemma) and continuous (Brouwer fixed point theorem) perspectives. In addition, we will see how this relates to some famous results like Nash equilibrium, Scarf’s lemma and hypergraphic stable matching.
-
3:30 - 4:00 pm EDTCoffee Break11th Floor Collaborative Space
March 24, 2023
-
3:30 - 4:00 pm EDTCoffee Break11th Floor Collaborative Space
March 25, 2023
There are no events currently scheduled for March 25th.
All event times are listed in ICERM local time in Providence, RI (Eastern Daylight Time / UTC-4).
All event times are listed in .
ICERM local time in Providence, RI is Eastern Daylight Time (UTC-4). 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.