Seminars and Colloquia by Series

Spatial mixing and the Swendsen-Wang dynamics

Series
Combinatorics Seminar
Time
Friday, September 18, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Antonio Blanca Pennsylvania State University

The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. The dynamics is a global Markov chain that is conjectured to converge quickly to equilibrium even at low temperatures, where the correlations in the system are strong and local chains converge slowly. In this talk, we present new results concerning the speed of convergence of the Swendsen-Wang dynamics under spatial mixing (i.e., decay of correlations) conditions. In particular, we provide tight results for three distinct geometries: the integer d-dimensional integer lattice graph Z^d, regular trees, and random d-regular graphs. Our approaches crucially exploit the underlying geometry in different ways in each case.

Spatial mixing and the Swendsen-Wang dynamics

Series
ACO Seminar
Time
Friday, September 18, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Antonio Blanca Pennsylvania State University

The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. The dynamics is a global Markov chain that is conjectured to converge quickly to equilibrium even at low temperatures, where the correlations in the system are strong and local chains converge slowly. In this talk, we present new results concerning the speed of convergence of the Swendsen-Wang dynamics under spatial mixing (i.e., decay of correlations) conditions. In particular, we provide tight results for three distinct geometries: the integer d-dimensional integer lattice graph Z^d, regular trees, and random d-regular graphs. Our approaches crucially exploit the underlying geometry in different ways in each case.

New Algorithms for Generalized Min Sum Set Cover

Series
ACO Student Seminar
Time
Friday, September 18, 2020 - 13:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/264244877/0166
Speaker
Majid FarhadiCS, Georgia Tech

We present a new rounding framework and improve the approximation bounds for min sum vertex cover and generalized min sum set cover, also known as multiple intents re-ranking problem. These classical combinatorial optimization problems find applications in scheduling, speeding up semidefinite-program solvers, and query-results diversification, among others.

Our algorithm is based on transforming the LP solution by a suitable kernel and applying a randomized rounding. It also gives a linear-programming based 4-approximation algorithm for min sum set cover, i.e., best possible due to Feige, Lovász, and Tetali. As part of the analysis of our randomized algorithm we derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which may be of independent interest.

Joint work with Nikhil Bansal, Jatin Batra, and Prasad Tetali. [arXiv:2007.09172]

Tropical convex hulls of polyhedral sets

Series
Student Algebraic Geometry Seminar
Time
Friday, September 18, 2020 - 09:00 for 1 hour (actually 50 minutes)
Location
Microsoft Teams Meeting
Speaker
Cvetelina HillGeorgia Tech

Please Note: Microsoft Teams Link: https://teams.microsoft.com/l/meetup-join/19%3a3a9d7f9d1fca4f5b991b4029b09c69a1%40thread.tacv2/1600180661071?context=%7b%22Tid%22%3a%22482198bb-ae7b-4b25-8b7a-6d7f32faa083%22%2c%22Oid%22%3a%223eebc7e2-37e7-4146-9038-a57e56c92d31%22%7d

Abstract: In this talk we introduce basic definitions in tropical convexity, and give an overview of some of the main results. The focus will then shift to joint work with Faye Pasley Simon and Sara Lamboglia on the interaction between tropical and ordinary convex hull. We will introduce results including the characterization of tropically convex polyhedra and give a lower bound on the degree of a fan tropical curve using only tropical techniques. The talk will conclude with some more recent results and several open questions.   

Geometry of nodal sets of Laplace eigenfunctions

Series
School of Mathematics Colloquium
Time
Thursday, September 17, 2020 - 11:00 for 1 hour (actually 50 minutes)
Location
https://us02web.zoom.us/j/89107379948
Speaker
Alexander LogunovPrinceton University

We will discuss geometrical and analytic properties of zero sets of harmonic functions and eigenfunctions of the Laplace operator. For harmonic functions on the plane there is an interestingrelation between local length of the zero set and the growth of harmonic functions. The larger the zero set is, the faster the growth of harmonic function should be and vice versa. Zero sets of Laplace eigenfunctions on surfaces are unions of smooth curves with equiangular intersections. The topology of the zero set could be quite complicated, but Yau conjectured that the total length of the zero set is comparable to the square root of the eigenvalue for all eigenfunctions. We will start with open questions about spherical harmonics and explain some methods to study nodal sets, which are zero sets of solutions of elliptic PDE. 

Zoom: https://us02web.zoom.us/j/89107379948

Reducing Isotropy to KLS: An n^3\psi^2 Volume Algorithm

Series
High Dimensional Seminar
Time
Wednesday, September 16, 2020 - 15:15 for 1 hour (actually 50 minutes)
Location
https://us02web.zoom.us/j/88203571169
Speaker
Santosh VempalaGeorgia Tech

Please Note: The preceding talk will be given on Tuesday September 15 at 10:30 am via https://technion.zoom.us/j/99202255210. More info here: http://people.math.gatech.edu/~glivshyts6/AGAonline.html

In this follow-up talk to the talk at the AGA seminar, we will discuss some aspects of a new algorithm for rounding and volume computation, including its proof, an efficient implementation for polytopes and open questions. We will begin the talk with a recap of the algorithm. 

Joint work with He Jia, Aditi Laddha and Yin Tat Lee. 

Link to attend: https://us02web.zoom.us/j/88203571169

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minors

Series
Graph Theory Seminar
Time
Tuesday, September 15, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Zi-Xia SongUniversity of Central Florida

Hadwiger's conjecture from 1943 states that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the early 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  In this talk, we show that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the Kostochka-Thomason bound. 

This is joint work with  Sergey Norin and Luke Postle.

A different approach to endpoint weak-type estimates for Calderón-Zygmund operators

Series
Analysis Seminar
Time
Tuesday, September 15, 2020 - 14:00 for 1 hour (actually 50 minutes)
Location
https://us02web.zoom.us/j/87104893132
Speaker
Cody StockdaleClemson

The weak-type (1,1) estimate for Calderón-Zygmund operators is fundamental in harmonic analysis. We investigate weak-type inequalities for Calderón-Zygmund singular integral operators using the Calderón-Zygmund decomposition and ideas inspired by Nazarov, Treil, and Volberg. We discuss applications of these techniques in the Euclidean setting, in weighted settings, for multilinear operators, for operators with weakened smoothness assumptions, and in studying the dimensional dependence of the Riesz transforms.

Probabilistic Method in Combinatorics

Series
Undergraduate Seminar
Time
Monday, September 14, 2020 - 15:30 for 1 hour (actually 50 minutes)
Location
Bluejeans meeting https://bluejeans.com/759112674
Speaker
Dr. Lutz WarnkeGeorgia Tech
The Probabilistic Method is a powerful tool for tackling many problems in discrete mathematics and related areas. Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property with positive probability. In this talk we shall give a gentle introduction to the Probabilistic Method, with an emphasis on examples.

L-space surgeries on 2-component L-space links

Series
Geometry Topology Seminar
Time
Monday, September 14, 2020 - 14:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/803706608
Speaker
Beibei LiuGeorgia Tech

All 3-manifolds can be described as surgery on links in the three-sphere by the celebrated theorem of Lickorish and Wallace. Motivated by the L-space conjecture, it is interesting to understand what surgery manifolds are L-spaces, which have the simplest possible Floer homology such as lens spaces. In this talk, we concentrate on surgeries on a family of links, which are called L-space links, and show possible L-space surgeries on such links. We also give some link detection results in terms of the surgeries. 

Pages