Discussion on several topics around the 2-2 games conjecture, the hypercontractive inequality and small set expansion.

Further reading: An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games by Ellis-Kindler-Lifshitz.

Background reading: On the Proof of the 2-to-2 Games Conjecture by Subhash Khot.

A code is a collection of strings over a finite alphabet (to put it simply). This fundamental object can exhibit far reaching mathematical properties as well as be of great practical value to protect data against errors. Codes are studied by different research communities such as theoretical computer science, combinatorics and electrical engineering. Despite much progress over the past decades, coding theory remains an incredibly active field. In this bootcamp talk, I plan to give a basic overview of some aspects of coding theory and discuss some active research directions.

One of the many successes of mathematics and computer science has been the introduction of graph expansion. A graph is expanding if it is simultaneously sparse and highly connected. Over the last few decades these objects have found applications in virtually all areas of theoretical computer science, and so they are a really important tool that should be in every theoretician's toolbelt. More recently, various high-dimensional analogous have been proposed and studied, which have led to many surprising applications (including in coding theory, the other focus of this reading group).

In this talk I want to first present some of the many different definitions of expansion. We will focus on the spectral definition of expanders and we will study some of its properties and applications. We will then turn to the world of high-dimensional expanders (HDXs). We will first introduce the notion of simplicial complexes (high dimensional analogues of graphs) and then define expansion on these. We will close the talk by describing some applications and connections of HDXs to other areas of theoretical computer science.

Error Correcting Codes are widely used to encode data in a robust (error-resilient) way. Locally Decodable Codes (LDCs) are a class of error correcting codes, where given the encoding E(x) of a string x, each bit of x can be recovered by just (randomly) querying a few bits of E(x). This property of local-decodability usually comes with a loss in “efficiency” of the code. In this talk, I will try to introduce LDCs and also talk about some tradeoffs between local-decodability and code efficiency.

A cactus representation of a graph, introduced by Dinitz et al. in 1976, is an edge sparsifier of $O(n)$ size that exactly captures all global minimum cuts of the graph. It is a central combinatorial object that has been a key ingredient in almost all algorithms for the connectivity augmentation problems and for maintaining minimum cuts under edge insertions (e.g. [Naor et al. SICOMP’97], [Cen et al. SODA’22], [Henzinger ICALP’95]). This sparsifier was generalized to Steiner cactus for a vertex set T , which can be seen as a vertex sparsifier of O(|T|) size that

captures all partitions of $T$ corresponding to a $T$-Steiner minimum cut, and also hypercactus, an analogous concept in hypergraphs. These generalizations further extend the applications of cactus to the Steiner and hypergraph settings.

In a long line of work on fast constructions of cactus and its generalizations, a near-linear time construction of cactus was shown by Karger and Panigrahi [SODA’09]. Unfortunately, their technique based on tree packing inherently does not generalize. The state-of-the-art algorithms for Steiner cactus and hypercactus are still slower than linear time by a factor of $\Omega(|T|)$ [Dinitz and Vainshtein STOC’94] and $\Omega(n)$ [Chekuri and Xu SODA’17], respectively.

We show how to construct both Steiner cactus and hypercactus using polylogarithmic calls to max flow, which gives the first almost-linear time algorithms of both problems. The constructions immediately imply almost-linear-time connectivity augmentation algorithms in the Steiner and hypergraph settings, as well as speed up the incremental algorithm for maintaining minimum cuts in hypergraphs by a factor of $n$.

The key technique behind our result is a novel variant of the very influential isolating min-cut technique [Li and Panigrahi FOCS’20, Abboud et al. STOC’21] which we called maximal isolating mincuts. This technique makes the isolating mincuts to be "more balanced" which, we believe, will likely be useful in many future applications.