Seminar

Title: Infinite matroids on lattices

Abstract: There are at least two well-studied ways to extend matroids to more general objects - one can allow the ground set to be infinite, or instead define the concept of independence on a lattice other than a set lattice. I will discuss some nice ideas that arise when combining these two generalizations. This is joint work with Andrew Fulcher.

Title: Recent Progresses on Correlation Clustering

Abstract: Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either "+" or "-", and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of - edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation. Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including "local to global correlation rounding" and "combinatorial preclusering". In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints. Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl.

Title: Sylvester-Gallai type configurations and Polynomial Identity Testing

Abstract: The classical Sylvester-Gallai theorem in combinatorial geometry says the following:

If a finite set of points in the Euclidean plane has the property that the line joining any two points contains a third point from the set, then all the points must be collinear. 

More generally, a Sylvester-Gallai (SG)-type configuration is a finite set of geometric objects with certain local dependencies. A remarkable phenomenon is that the local constraints give rise to global dimension bounds for linear SG-type configurations, and such results have found far reaching applications to complexity theory and coding theory. In particular, SG-type configurations have been extremely useful in applications to Polynomial Identity Testing (PIT), a central problem in algebraic complexity theory.

In this talk, we will discuss non-linear generalizations of SG-type configurations which consist of polynomials. We will discuss how uniform bounds on SG-configurations give rise to deterministic poly-time algorithms for the PIT problem. I’ll talk about results showing that these non-linear SG-type configurations are indeed low-dimensional as conjectured by Gupta in 2014. This is based on joint works with A. Garg, R. Oliveira and S. Peleg.

Title: Reconstructing Shredded Random Matrices

Abstract: The Graph Reconstruction Conjecture states that if we are given the set of vertex-deleted subgraphs of some graph, then there is a unique graph G that can be reconstructed from them. This conjecture has been open since the 60s, and has only been solved for certain classes of graphs with not much progress towards the general case. We instead study adjacent reconstruction problems, for example, studying matrices instead of graphs:  Given some binary matrix M, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the original matrix and will it be unique? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that for matrices with entries that are i.i.d. Bernoulli(p), that for p >2log(n)/n that the matrix is indeed unique with high probability. This is a joint work with Caelan Atamanchuk and Luc Devroye.

Title: Adventures in Enumeration

Abstract: We make the argument that by combining pure mathematical tools with computational insights and applications from a vast array of disciplines, combinatorics is the perfect area to see all the wonders of math on display. Applications discussed include the analysis of classical algorithms, restricted permutations, models predicting the shape of biomembranes, queuing theory, random walks, ratchet models for gene expression, maximum likelihood degree in algebraic statistics, transcendence of zeta values, sampling algorithms for perfect matchings in bipartite graphs, and parallel synthesis for DNA storage.

Title: Configuration spaces and combinatorial algebras

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Abstract:  In this talk, I will discuss connections between configuration spaces, an important class of topological space, and combinatorial algebras arising from the theory of reflection groups. In particular, I will present work relating the cohomology rings of some classical configuration spaces—such as the space of n ordered points in Euclidean space—with Solomon’s descent algebra and the peak algebra. The talk will be centered around two questions.

First, how are these objects related?

Second, how can studying one inform the other? This is partially joint work with Marcelo Aguiar and Vic Reiner.

Title: Stochastic  Oracles and Where to Find Them

Abstract: Continuous optimization is a mature field, which has recently undergone major expansion and change. One of the key new directions is the development of methods that do not require exact information about the objective function. Nevertheless, the majority of these methods, from stochastic gradient descent to "zero-th order" methods use some kind of approximate first order information. We will overview different methods of obtaining this information, including simple stochastic gradient via sampling, robust gradient estimation in adversarial settings, traditional and randomized finite difference methods and more.

We will discuss what key properties of these inexact, stochastic first order oracles are useful for convergence analysis of optimization methods that use them. 

Title: Deza graphs and vertex connectivity

Abstract: A k-regular graph on v vertices is called a Deza graph with parameters (v, k, b, a), b ≥ a if the number of common neighbors of any two distinct vertices takes two values: a or b. A Deza graph is called a strictly Deza graph if it has diameter 2 and is not strongly regular.

In this talk we will discuss the enumeration of strictly Deza graphs and the enumeration of special subclass of strictly Deza graphs called divisible design graphs. We will also describe the constructions of divisible design graphs found during the enumeration.

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 2

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 1

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.