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).

We discuss an algorithm for sorting binary labels on a poset in the LCA model of Rubinfeld et al and Alon et al (ICS'11, SODA’12), and several applications of this algorithm. The LCA is a local corrector for monotonicity — an algorithm that makes lookups to some unknown function and answers queries to a nearby monotone function — and runs in time polynomial in the degree of the DAG that corresponds to the poset. We will also discuss an extension of this algorithm that allows for local correction of real-valued functions, and the first of the applications, which is a tolerant monotonicity tester (and multiplicative+additive-error distance approximator) for functions over general posets. Our algorithm is built on a body of work on distributed greedy graph algorithms; specifically we rely on a recent work of Ghaffari (FOCS'22), which gives an efficient LCA for computing maximal matchings.

The other application turns our focus to the Boolean hypercube, where we can use LCAs as subroutines for tolerant testing or for proper learning under the uniform distribution in 2^{\tilde{O}(\sqrt{n})} time and samples. We will first discuss using the local corrector to upgrade an improper learner to a proper learner in the realizable setting, then discuss a different LCA-based approach to proper learning in the agnostic setting. The learning algorithms match the query complexity lower bound of Blais et al (RANDOM ’15) and are optimal in their dependence on n, and optimality of the testing algorithm is an open problem (see the recent “mildly exponential" lower bound of Chen et al (STOC’24)).

Abstract: Graph counting lemma of Chung, Graham, and Wilson (Combinatorica 1988) is a fundamental result in combinatorics, which states that if a large graph is pseudorandom, then the number of copies of any small graph $H$ in $G$ is close to what is expected from a random graph of the same density. However, this result is only nontrivial when $G$ is a dense graph. In this work, we obtain a counting lemma that works in the sparse setting, and it is well-suited for the density increment arguments in additive combinatorics. In a recent remarkable breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. We combine our counting lemma with other ideas to establish Kelley--Meka type bounds for all linear patterns defined by translation-invariant systems of binary linear forms, i.e., each form depends on exactly two variables. In particular, we obtain strong bounds for the Turan problem in Abelian Cayley sum graphs, i.e. an upper bound on the maximum edge density of an Abelian Cayley sum graph with a clique of a given size. To prove our results, we employ some of the recent technology developed by Kelley and Meka and also the follow-up work by Kelley, Lovett, and Meka (STOC 2024).

This talk is based on a joint work with Yuval Filmus, Hamed Hatami and Kaave Hosseini (FOCS 2024).

We discuss the connection between isoperimetric inequalities, their "directed" analogues, and monotonicity testing. A series of works in the Boolean setting of testing monotonicity of functions $f : \{0,1\}^d \to \{0,1\}$ has leveraged an emerging connection between isoperimetric inequalities (such as Poincaré, Margulis and Talagrand inequalities) and "directed analogues" of such inequalities to obtain monotonicity testers with improved query complexity. This connection, first observed by Chakrabarty and Seshadhri (STOC 2013), also underlies the result of Khot, Minzer and Safra (FOCS 2015), who gave a nearly optimal nonadaptive tester making roughly $\sqrt{d}$ queries.

Classical isoperimetric inequalities hold on both continuous and discrete domains, and indeed have one of their roots in the work of Poincaré on mathematical physics. Moreover, similar techniques are relevant to both settings, e.g. Fourier analysis. Therefore, toward a deeper understanding of the connection between classical and directed isoperimetry, we wish to understand whether directed isoperimetry is also a feature of the fully continuous setting $f : [0,1]^d \to \bR$ -- and moreover, whether this has algorithmic implications for monotonicity testing. We will discuss a pair of works in this direction (RANDOM 2023 and FOCS 2024), first showing that the ideas behind the classic "edge tester" carry over to the continuous case, and then showing that the mathematical physics interpretation of the classical Poincaré inequality (as characterizing the convergence of the heat equation) reveals also a proof of a directed Poincaré inequality, which implies a tester for the continuous setting making roughly $\sqrt{d}$ queries. Another takeaway from the latter result is that tools from optimal transport prove to be useful for tensorization, i.e. promoting one-dimensional results to high dimension at no loss.