From Cuts to Convexity & Beyond

Honoring Michel Goemans at 60

Please join us for a one-day celebration of Professor Michel Goemans and his 60th birthday. Michel has made groundbreaking contributions to combinatorial optimization, graph theory, approximation algorithms, and more. This event aims to showcase and celebrate the many areas of mathematics close to Michel's heart.

Please register for this event here.

Speakers:

• Nick Harvey (University of British Columbia)
• Jon Kleinberg (Cornell University)
• Thomas Rothvoss (University of Washington)
• Ola Svensson (EPFL)
• David P. Williamson (Cornell University)
• Jan Vondrák (Stanford University)
• Rico Zenklusen (ETH Zürich)

Schedule:

Event Poster:

Titles & Abstracts:

• Nick Harvey (University of British Columbia)
  
  • Title: Explicit Orthogonal Arrays with Arbitrary Parameters
  • Abstract: Orthogonal arrays are a type of combinatorial design that emerged in the 1940s in the design of statistical experiments. In 1947, Rao proved a lower bound on the size of any orthogonal array, and raised the problem of constructing arrays of minimum size. Kuperberg, Lovett and Peled (2017) gave a non-constructive existence proof of orthogonal arrays whose size is near-optimal (i.e., within a polynomial of Rao's lower bound), leaving open the question of an algorithmic construction. I will present recent work with Arvin Sahami, in which we give the first explicit, deterministic, algorithmic construction of orthogonal arrays achieving near-optimal size for all parameters.


• Jon Kleinberg (Cornell University)
  
  • Title: AI's Models of the World, and Ours
  • Abstract: The power of generative AI is in some sense a simultaneous practical success and theoretical mystery -- we are lacking good conceptual explanations for the performance of these systems on a number of important tasks. Like many compelling mysteries with this flavor that the field has encountered over the years, it has acted as a kind of call to action for the theory of computing, which has begun to address these questions at multiple layers of abstraction: both to study the effect of fine-grained architectural decisions in the underlying models, and at a higher level, to formalize the core theoretical properties of basic primitives like language generation itself. We discuss a set of questions at this higher level, including the search for well-defined "world models" implicit in generative models trained on data; the minimal assumptions needed to prove guarantees for such models; and the behaviors that result when models of vastly different levels of power try to interact on shared tasks.
    
    The talk will include joint work with Ashton Anderson, Karim Hamade, Reid McIlroy-Young, Siddhartha Sen, Justin Chen, Sendhil Mullainathan, Ashesh Rambachan, and Keyon Vafa.


• Thomas Rothvoss (University of Washington)
  
  • Title: Bounds on the Extension Complexity of Polytopes
  • Abstract: A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. The minimum number of constraints needed is called the extension complexity. We will survey the development and the tremendous success of this field over the past decade-and-a-half including tight bounds for the permutahedron and exponential lower bounds for the correlation polytope and the matching polytope.


• Ola Svensson (EPFL)
  
  • Title: Chasing Lower Bounds: In Michel's Footsteps and in Online Edge Coloring
  • Abstract: Michel Goemans sets a high bar, both with his groundbreaking algorithms and surprisingly fast jogs, a standard that has inspired many, including myself.
    
    This talk focuses on online edge coloring, where the goal is to approach Vizing's offline bound of Δ+1 colors despite edges arriving sequentially. A simple greedy algorithm uses 2Δ−1 colors, which Bar-Noy, Motwani, and Naor [IPL'92] showed is optimal for deterministic algorithms when Δ=O(log n) and for randomized algorithms when Δ=O(√log n​). They conjectured, however, that for Δ=ω(log n), randomized algorithms could achieve (1+o(1))Δ colors.
    
    We recently resolved this conjecture affirmatively. Further developing these techniques allows us to establish sharp thresholds matching the aforementioned impossibility results:
    • We give a deterministic online algorithm achieving (1+o(1))Δ-colorings for all Δ=ω(log n).
    • We give a randomized algorithm achieving (1+o(1))Δ-colorings already when Δ=ω(√log n​).
    
    (Joint work with Joakim Blikstad, Radu Vintan, and David Wajc.)


• David P. Williamson (Cornell University)
  
  • Title: The 4/3 Conjecture for the Traveling Salesman Problem: A Status Update with Digressions
  • Abstract: The 4/3 conjecture for the traveling salesman problem (TSP) states that the standard linear programming relaxation for the TSP has an integrality gap of 4/3 in the case of the symmetric TSP instances that obey the triangle inequality. In this talk, I will survey what we know about the status of this conjecture and special cases for which we know that the conjecture is true. As time allows, I will also indulge in some digressions about work that Michel and I did together.


• Jan Vondrák (Stanford University)
  
  • Title: From Spanning Trees to Submodular Functions and Nash Social Welfare
  • Abstract: I will talk about how my early work with Michel influenced my later thoughts. I will start with an old paper with Michel about spanning trees, and how it can be viewed through the lens of expectations of submodular functions. Understanding the behavior of submodular functions over product distributions led later to the idea of a multilinear relaxation, and a new algorithmic framework for optimization of submodular functions. Finally, I will survey some other applications of this relaxation, and a recent result for optimization of Nash social welfare.


• Rico Zenklusen (ETH Zürich)
  
  • Title: Ghost Value Augmentation for k-Edge-Connectivity
  • Abstract: We show that every edge-weighted, fractionally k-edge-connected graph can be rounded in polynomial time to an integral (k-O(1))-edge-connected graph of no greater cost. This result has several implications for minimum edge-connected subgraph problems. In particular, it resolves an open question of Pritchard, which aims to generalize a result of Gabow, Goemans, Tardos, and Williamson for the unweighted case. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems.
    
    This is joint work with Ellis Hershkowitz and Nathan Klein.

Michel's Former License Plate:

Organizers: Nick Harvey, Thomas Rothvoss, John Urschel, David P. Williamson, Jan Vondrák
Contact Email: urschel@mit.edu
Organized in collaboration and with the support of the MIT Mathematics Department