ACO Seminar - Marcus Michelen and Shayan Oveis Gharan

— 5:00pm

Location:
In Person - Wean Hall 8220 (special time)

Speaker:
MARCUS MICHELEN and SHAYAN OVEIS GHARAN

Two Talks

There will be two back-to-back talks during this week's seminar.

2:30 pm
► Marcus Michelen     

Assistant Professor, Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago      

— New lower bounds for sphere packings and independent sets via randomness 

We construct new lower bounds for sphere packings in high dimensions and for independent sets in graphs with not-too-large co-degrees. For dimension d, this achieves a sphere packing of density (1 + o(1)) d log d / 2(d+1). In general dimension this provides the first asymptotically growing improvement for sphere packing lower bounds since Rogers' bound of c*d/2d in 1947. The proof amounts to a random (very dense) discretization together with a new theorem on constructing independent sets on graphs with not-too-large co-degree. Both steps will be discussed and no knowledge of sphere packings will be assumed or required. Central to the analysis is a nibble method. 

This is based on joint work with Marcelo Campos, Matthew Jenssen andJulian Sahasrabudhe.

4:00 pm
► Shayan Oveis Gharan      

Lazowska Professor of Computer Science & Engineering Computer Science and Engineering, University of Washington      

— C-Lorentzian Polynomials, Trickledown Thms, Mixing Time and Log Concavity 

Completely Log Concave, a.k.a., Lorentzian polynomials, were discovered a few years ago where they were used to relate seemingly distant areas of Math and CS such as geometry of polynomials, Hodge theory for combinatorial geometries, theory of high dimensional expanders and mixing time of Markov chains. Consequently, they lead to a resolution of several long-standing open problems on matroids such as the Mason's log-concavity conjecture and the Mihail-Vazirani conjecture on the expansion of the bases exchange graph. Unfortunately, this family of polynomials are limited as their support corresponds to bases of a matroid or more generally vertices of a generalized permutahedra. I will explain a generalization of Lorentzian polynomial to convex cones in the positive orthant, called C-Lorentzian polynomials, and use them to study combinatorial objects such as distributive, modular, or geometric lattices and the corresponding sampling, and log-concavity problems. Enroute we will also discuss new local-to-global theorems for high-dimensional expanders called Trickledown theorems. 

Based on a joint work with Jonathan Leake and Kasper Lindberg. 3:30 pm - Jane Street-sponsored tea and cookies in the Math Lounge. Please bring your own mug if possible.

Event Website:
https://aco.math.cmu.edu/seminar.html

Add event to Google
Add event to iCal