Over the past few years we have seen many exciting breakthroughs in the areas of coding theory and expanders. In this reading group we will explore some of them.

This reading group is open to all members of the Princeton and IAS community. We have two types of talks: bootcamp talks (), where the goal is to introduce the foundations of some topic to people that might not have seen it before; and specialized talks (), where a paper is presented and discussed. We highly encourage everyone interested in theoretical computer science to show up to the bootcamp talks.

New format! Each talk will be divided into two 1-hour sessions. The first session will provide an overview and introduction to the topic or paper, while the second session will delve into technical details. If you're not particularly interested in the topic, you may consider skipping the second session. Please note that some talks will only consist of the first session.

We encourage (but not require) everyone to give a talk on their favorite subject related to the reading group topics, this can be one of your papers or someone else's paper. If you need some suggestions feel free to check the reading list below.

Organized by Fernando Granha Jeronimo (IAS) and Pedro Paredes (Princeton). Please contact us if you have any questions or if you want to give a talk.


FAQ

Q: When/where is the reading group?
A: Every Monday from 5:00pm to 6:00pm/7:00pm in either room CS 302 at Princeton or Rubenstein Commons Meeting Room 5 at the IAS. See the schedule below for more information. New times and room!

Q: I'm an undergad/grad student/postdoc/visitor in computer science/math/physics at Princeton/IAS, can I show up?
A: Yes! Everyone is welcome.


Next Talk

May 01, 2023, 5:00pm | Rubenstein Commons Meeting Room 5 at IAS

Elyassaf Loyfer (Hebrew University)

An elementary proof of the first LP bound for binary codes

The asymptotic rate vs. distance problem is a long-standing fundamental problem in coding theory. The best upper bound to date was given in 1977 and has received numerous proofs and interpretations. Here we provide a new, elementary proof of this bound based on counting walks in the Hamming cube.

Joint work with Nati Linial.


Spring 23 Schedule

Lower bounds for general LDC

Pei Wu (IAS)

February 20, 2023, 5:00pm | Rubenstein Commons Meeting Room 5 at IAS

Last semester, we learned lower bounds for linear locally decodable codes with 2 queries. This time, let us see how to generalize some of the ideas to general LDCs.

Expansion, Codes and Optimization at the Frontiers

Fernando Granha Jeronimo (IAS)

February 27, 2023, 5:00pm | CS 302 at Princeton

Expanders are highly connected, but sparse graphs. By combining these opposing properties, they found a plethora of applications both in theory and in practice. Codes are objects that enable the protection of data against corruptions thereby being instrumental in communication and storage. Optimization underlies much of our understanding of efficient computation. Despite the fundamental nature of these areas, much is either being discovered or yet to be discovered In this talk, we will discuss how synergistic interactions among expansion, codes and optimization led to recent progress on our understanding of almost optimal codes and almost optimal expanders. We will also mention future directions along these frontiers.

Modern Expanders Bootcamp II - Other notions of expansion

Pedro Paredes (Princeton)

March 06, 2023, 5:00pm | CS 302 at Princeton

In the Fall semester we discussed an introduction to expanders and we also talked about high dimensional expansion. One topic we only briefly mentioned, but that has become increasingly more popular with the recent breakthroughs on locally testable codes (which we will hopefully discuss in a future reading group talk), is the concept of vertex expanders.

In the first hour of the talk I plan to recall the definitions of vertex expansion and then I will spend some time showing some known properties of these objects. Time permitting, I will show one application of vertex expanders to constructing codes.

In the second hour of the talk I want to talk about a similar notion of expansion called unique-neighbor expansion and in particular I will present some results from a recent paper of mine: https://arxiv.org/pdf/2302.01212.pdf I plan to make this second hour self contained for those that miss the first part, and I also plan to keep it at the introductory level so everyone can take something from the talk.

Bipartite Ramanujan Graphs of All Degrees

Pachara Sawettamalya (Princeton)

March 27, 2023, 5:00pm | Rubenstein Commons Meeting Room 5 at IAS

We say that a $d$-regular graph is Ramanujan if all of its non-trivial eigenvalues lie between $\pm 2\sqrt{d-1}$. This bound is, in fact, tight due to the well-known Alon-Boppana Bounds. In this talk, we will discuss the first elegant-yet-simple breakthrough by Marcus, Spielman, Srivastava which shows the existence of (regular) bipartite Ramanujan graphs of all degrees. Almost all of the key ingredients in this paper are surprisingly simple; thus, no background is required.

Reference:

A. Marcus, D. A. Spielman and N. Srivastava, "Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees".

Matching Vector Codes

Manik Dhar (Princeton)

April 10, 2023, 5:00pm | Rubenstein Commons Meeting Room 5 at IAS

We will describe the current state of the art construction of constant query LDCs using matching vectors. In the first hour we give the construction of the codes assuming the existence of matching vector families.

In the second hour we will sketch the construction of matching vector families using representations of OR mod 6.

Robust sublinear expanders

Matija Bucic (Princeton and IAS)

April 24, 2023, 5:00pm | CS 302 at Princeton

Expander graphs have been perhaps one of the most widely useful classes of graphs ever considered. In this talk we will focus on a fairly weak notion of expanders called sublinear expanders, first introduced by Komlos and Szemeredi around 25 years ago. They have found many remarkable applications ever since. In particular we will focus on certain robustness conditions one may impose on sublinear expanders while still maintaining their most useful property, the fact that in any graph one can find a sublinear expander subgraph of almost the same density. We will discuss a number of useful properties of such robust sublinear expanders and mention some applications.

An elementary proof of the first LP bound for binary codes

Elyassaf Loyfer (Hebrew University)

May 01, 2023, 5:00pm | Rubenstein Commons Meeting Room 5 at IAS

The asymptotic rate vs. distance problem is a long-standing fundamental problem in coding theory. The best upper bound to date was given in 1977 and has received numerous proofs and interpretations. Here we provide a new, elementary proof of this bound based on counting walks in the Hamming cube.

Joint work with Nati Linial.


Reading list

Here is a (nonexhaustive) list of suggested papers for this reading group:


Fall 2022 Schedule

2-2 games conjecture, hypercontractivity and small set expansion

Noam Lifshitz (IAS)

November 07, 2022, 5:30pm | CS 402

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.

Modern Coding Theory Bootcamp I

Fernando Granha Jeronimo (IAS)

November 14, 2022, 5:30pm | CS 402

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.

Modern Expanders Bootcamp I

Pedro Paredes (Princeton)

November 28, 2022, 5:30pm | CS 402

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.

Introduction to Locally Decodable Codes

Kunal Mittal (Princeton)

December 05, 2022, 5:30pm | CS 402

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.

Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts

Zhongtian He (Princeton)

December 12, 2022, 5:30pm | CS 402

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.

TCS @ Princeton + IAS

Copyright © 2022-23