ICTS

We will talk about a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. These constructions often proceed by showing that the distance of local constant-sized codes can be lifted to a distance lower bound for the global code. The regularity framework allows us to similarly lift list size bounds for local base codes, to list size bounds for the global codes.

This allows us to obtain novel combinatorial bounds for list decoding and list recovery up to optimal radius, for Tanner codes of Sipser and Spielman, and for the distance amplification scheme of Alon, Edmonds, and Luby. Further, using existing algorithms for computing weak-regularity decompositions of sparse graphs in (randomized) near-linear time, these tasks can be performed in near-linear time.

Based on joint work with Madhur Tulsiani.
DIMACS (Rutgers University) and Institute for Advanced 

In this talk, we consider the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength $N = 2^m$, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in $m$.

A k-wise m-divisible set family is a collection F of subsets of {1,...,n} such that any intersection of k sets in F has cardinality divisible by m. If k=m=2, it is well-known that |F| <= 2^{[n/2]}. We generalise this by proving that |F| <= 2^{[n/p]} if k=m=p, for any prime number p.
For arbitrary values of m, we prove that (4m^2)-wise m-divisible setfamilies F satisfy |F| <= 2^{[n/m]} and that the only families achieving the upper bound are atomic, meaning that they consist of all the unions of disjoints subsets of size m. This improves upon a recent result by Gishboliner, Sudakov and Timon, that arrived at the same conclusion for k-wise m-divisible families, with values of k that behave exponentially in m.
Our techniques rely heavily upon a coding-theory analogue of Kneser's Theorem from additive combinatorics.
Joint work with Chenying Lin.
 

The theory of probabilistically checkable proofs (PCPs) shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. The PCP Theorem [ALMSS] is a fundamental result in computer science with far-reaching consequences in hardness of approximation, cryptography, and cloud computing. A PCP has two important parameters: 1) the size of the encoding, and 2) soundness, which is the probability that the verifier accepts an incorrect proof, both of which we wish to minimize. In 2005, Dinur gave a surprisingly elementary and purely combinatorial proof of the PCP theorem that relies only on tools such as graph expansion, while also giving the first construction of 2-query PCPs with quasi-linear size and constant soundness (close to 1). Our work improves upon Dinur's PCP and constructs 2-query, quasi-linear size PCPs with arbitrarily small constant soundness. As a direct consequence, assuming the exponential time hypothesis, we get that no approximation algorithm for 3-SAT can achieve an approximation ratio significantly better than 7/8 in time 2^{n/polylog n}. In this talk, I will introduce PCPs and discuss the components that go into our proof. This talk is based on joint work with Dor Minzer and Nikhil Vyas, with an appendix by Zhiwei Yun.

The coboundary expansion property of tensor product codes, also known as product expansion, plays an important role in the discovery of good quantum LDPC codes and classical locally testable codes. Prior research has shown that this property is equivalent to agreement testability and robust testability for products of two codes with linear distance. However, for products of more than two codes, it is a strictly stronger property.

In this talk, I will outline key ideas underlying a recent result establishing that tensor products of an arbitrary number of random codes over sufficiently large fields exhibit strong coboundary expansion. This result suggests promising directions for new quantum locally testable code constructions.

In recent years there is a growing interest in higher dimensional random complexes, both as natural extensions of random graphs, and as potential tools for new applications, e.g. to higher dimensional expanders. We will focus on two models of random complexes and their generic topological properties:

1. A classical theorem of Alon and Roichman asserts that the Cayley graph C(G,S) of a group G with respect to a logarithmic size random subset S of G is a good expander. We consider a k-dimensional analogue of Cayley graphs, called Balanced Cayley Complexes, discuss the spectral gap of their (k-1)-Laplacian and in particular obtain a high dimensional version of the Alon-Roichman theorem.

2. A permutation complex is the order complex of the intersection of two linear orders. We describe some properties of these complexes and discuss bounds on the probability that a permutation complex associated with random orders is topologically k-connected.
Joint work with Omer Moyal.

I will talk about proximity gaps for Reed-Solomon codes. In particular we will discuss questions of the following kind: How many points of an affine space can be "close" in Hamming distance to the Reed-Solomon code?

We will see how to use an understanding of this, to effectively analyze interactive protocols for testing if a given function is close to a Reed-Solomon Codeword.

TBD

Paraphrasing the title of Riemann’s famous lecture of 1854 I ask: What is the most rudimentary notion of a geometry? A possible answer is a path system: Consider a finite set of “points” x_1,…,x_n and provide a recipe how to walk between x_i and x_j for all i\neq j, namely decide on a path P_ij, i.e., a sequence of points that starts at x_i and ends at x_j, where P_ji is P_ij, in reverse order. The main property that we consider is consistency. A path system is called consistent if it is closed under taking subpaths. What do such systems look like? How to generate all of them? We still do not know. One way to generate a consistent path system is to associate a positive number w_ij>0 with every pair and let P_ij be the corresponding w-shortest path between x_i and x_j. Such a path system is called metrical. It turns out that the class of consistent path systems is way richer than the metrical ones. My main emphasis in this lecture is on what we don’t know and wish to know, yet there is already a considerable body of work that we have done on the subject. The new results that I will present are joint with my student Daniel Cizma as well as with him and with Maria Chudnovsky

We consider the fundamental trade-off between the compactness of information representation and the efficiency of information extraction in the context of the set membership problem. In this problem, a set S of size at most n, drawn from a universe of size m, is to be represented as a short bit vector to answer membership queries of the form “Is x in S?” by probing the bit vector at t positions. The bit-probe complexity s(m, n, t) denotes the minimum number of bits of storage needed for such a scheme. We are interested in determining the value of s(m, n, t). Over the past two and a half decades, Jaikumar has made foundational contributions that have shaped much of the work in this area. In this talk, we focus on the two-probe case (t = 2), where, in joint work with Jaikumar, we improve upon a result of Alon and Feige (2009) to obtain fairly tight upper and lower bounds on s(m, n, t=2). Interestingly, both the upper and lower bounds rely on combinatorial analyses involving graphs of large girth.

We present an inequality relating linear combinations of mutual information between subsets of mutually independent random variables and an auxiliary random variable (in the spirit of Shearer’s Lemma or Han’s inequality). By suitable choices of the auxiliary random variable, one can use this to obtain several previously known results as consequences: a) A generalized Stam’s inequality that implies the monotonicity of the entropy power b) Strong data-processing constants between sums of i.i.d. random variables c) Rusza-type sub-modular inequalities on sums of independent random variables defined on finite Abelian groups.

Randomness extractors take a short truly random seed and use it to extract a longer, almost uniform, string from a weak source that has k bits of (min) entropy. How short can the short random seed be? It is not hard to show that it has to be Omega(log (n/eps)), where n is the number of bits of the weak source and eps is an error parameter. Good enough right? I would say it is, but Jaikumar Radhakrishnan and Amnon Ta-Shama showed it is log (n-k) + 2log(1/eps)-O(1) and this is tight up to the additive constant in the sense that a random graph with these parameters is an extractor. As a belated thanks I am going to explain the role this result has played in the zig-zag construction of extractors, leading to zig-zag expanders, SL=L (among other results), yada yada yada, a position in Stanford, multicalibration and its applications.

I shall present a mathematical basis for the model collapse phenomenon observed in recursive training of neural networks.

Let $v_1$, $v_2$, ..., $v_n$ be real numbers whose squares add up to 1.  Consider the $2^n$ signed sums of the form $S = \sum \pm v_i$.  In 1986, Boguslav Tomaszewski asked whether it is always true that at least half of these sums satisfy $|S| \le 1$.  In 2020, Nathan Keller and Ohad Klein proved that the answer is yes.  In this talk, we will discuss some of the tools used to solve this problem.

One of Alan Turing's most influential papers is his 1950 Computing machinery and intelligence, in which he introduces the famous "Turing test" for probing the nature of intelligence by evaluating the abilities of machines to behave as humans. In this test, which he calls the "Imitation Game," a (human) referee has to distinguish between two (remote and separate) entities, a human and a computer, only by observing answers to a sequence of arbitrary questions to each entity. This lecture will exposit, through examples from a surprisingly diverse array of settings, the remarkable power of this basic idea to understand many other concepts. I will discuss variations of the Imitation Game in which we change the nature of the referee, and of the objects to be distinguished, to yield different analogs of the Turing test. These new Imitation Games lead to novel, precise, and operative definitions of classical notions, including secret, knowledge, privacy, randomness, proof, fairness, and others. These definitions have in turn led to numerous results, applications, and understanding. Some, among many consequences of this fundamental paradigm, are the foundations of cryptography, the surprising discoveries on the power and limits of randomness, the recent influential notion of differential privacy, and breakthrough results on patterns in the prime numbers and navigation in networks. Central to each of these settings are computational and information theoretic limitations placed on the referee in the relevant Imitation Game. This lecture will survey some of these developments. It assumes no specific background knowledge.

In this talk I will give an alternate proof for Bourgain's theorem for metric embeddings. The proof is combinatorial and achieves a sharper bound on the distortion.

As we know, Jaikumar is a master at wielding entropy in the most elegant and surprising ways. In honor of Jaikumar (and entropy), I will describe a recent result with Josh Brakensiek showing that every constraint satisfaction problem (CSP) can be sparsified down to (within polylog factors of) the size of a maximum non-redundant instance of that CSP. A non-redundant instance of a CSP admits, for each constraint, an assignment satisfying only that constraint, making such instances obvious barriers for sparsification (e.g., for cut sparsification in graphs, spanning trees are non-redundant instances).

Our sparsification theorem is established in the very general context of set families. A key technical ingredient is an application of the beautiful entropic inequality underlying Gilmer's recent breakthrough on the union-closed sets conjecture.

As a consequence of our main theorem, which precisely ties the sparsifiability of a CSP to its non-redundancy (NRD), a number of results in the NRD literature immediately extend to CSP sparsification. We also contribute new results towards understanding the rich landscape of NRD of CSP predicates. For example, in recent work with Brakensiek, Jansen, Lagerkvist and Wahlstrom, we demonstrate for every rational r \ge 1, an example CSP with NRD growing as n^r. The upper bound is proved using Shearer's lemma.

In this talk we review some applications of the powerful idea of rejection sampling in source-coding and beyond. We start with the classical case, move to the classical-quantum case and then to the (fully) quantum case.