The seminal work of Karger and Benczur and Karger from the 90s showed that graphs can be "sparsified" to a number of edges nearly linear in the number of vertices, so that every cut is preserved to within multiplicative factors close to 1. In the years since, graph (and hypergraph) sparsification has emerged as a central tool in the algorithmic literature, with numerous applications to streaming, fully dynamic algorithms, and more. The utility of this idea frames the natural question of which other combinatorial objects are amenable to sparsification. In this talk, I will provide a partial answer through the recently introduced notion of "code sparsification" which provides a unified framework to construct graph / hypergraph sparsifiers, while also yielding new sparsifications for CSPs and Cayley graphs. Specifically, the given structure to be preserved is a linear error correcting code; the goal is to select a re-weighted subset of the coordinates of the code such that the Hamming weight of every codeword is preserved within multiplicative factors close to 1. We show that this class of problems gives the right language to abstract the techniques of Karger and Benczur and Karger --- and indeed all codes can be sparsified to length nearly linear in the number of message bits. This generalization already resolves some basic questions in CSP sparsification. A further generalization to additive codes over finite abelian groups gives even more powerful results and in particular completely classifies the class of symmetric Boolean CSPs that allow nearly linear sized sparsification. Finally, by developing a linear algebraic analog of spanning trees, all of these sparsifiers become efficiently constructible.

Based on joint works with Sanjeev Khanna (Penn) and Madhu Sudan (Harvard).

With massive graphs becoming increasingly prevalent, there has been growing interest in sparsifiers which preserve certain properties of graphs while having a small number of edges. The Edge Degree Constrained Subgraph (EDCS), introduced by Bernstein and Stein (2015, 2016), is such a sparsifier that approximately preserves the size of the maximum matching. EDCS is extremely robust as it remains a good sparsifier under various operations. Consequently, it has found applications in a myriad of different settings including the dynamic, streaming, and sublinear time settings, as well as in the communication model, stochastic matching, and massively parallel computations (MPC).

EDCS is often used to obtain 2/3-approximate matchings. However, we showed in a recent work that it is powerful enough to obtain a much better 5/6-approximation in the robust communication model, significantly improving over prior bounds. The talk will present this result while also covering the basic properties of EDCS.

Based on joint works with Behnezhad (2023), and Behnezhad and Roghani (2024).

We will discuss sublinear-time algorithms that approximate the graph's arboricity (and other similar density measures) with near-optimal query complexity, including a work of Eden, Mossel, and Ron from SODA'22 that provides an O(log^2 n) approximation and a very recent work with Jiangqi Dai and Julian Portmann that provides an O(1) approximation.

In the fully dynamic matching problem, the goal is to efficiently maintain an (approximate) maximum matching of a graph that is subject to edge insertions and deletions. In this talk, I will overview a recent approach that (conditionally) resolves some longstanding barriers for this problem using graph sparsification. Along the way, I will discuss connections to Ruzsa-Szemerédi (RS) graphs, and a generalization of them called Ordered RS graphs, that have played extremely important roles in many recent sublinear algorithms and lower bounds.

Based on a joint work with Alma Ghafari (2024).