Talks

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.

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 this talk, we will introduce interactive oracle proofs (IOPs), which are an interactive generalization of probabilistically-checkable proofs (PCPs). IOPs can then be “compiled” into very efficient cryptographic proofs, which can be very short (say, polylogarithmic length) and admit very efficient verifiers (say, polylogarithmic time). One requirement that arises from practice is that the prover also be very efficient; ideally, running in linear time.

After introducing these concepts, I will outline how one can use error-correcting codes with efficient encoding algorithms to design efficient cryptographic proofs. We will then discuss Repeat-Accumulate-Accumulate (RAA) codes, which are a simple class of turbo codes offering extremely efficient encoding and near-GV bound minimum distance. We will spend a good portion of this presentation describing these codes, discussing the challenges which arise in their analysis, and surveying some open problems.

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.

The advent of gravitational wave (GW) detections has opened a new window into our understanding of stellar-mass black holes and neutron stars. Ongoing advancements and upcoming third-generation GW detectors are expected to provide increasingly detailed insights into the properties of compact object binaries across cosmic time. In this context, the merger rate density inferred from GW detections can be interpreted as the convolution of the cosmic star formation history, chemical evolution, and binary stellar evolution.
Studying this connection from the perspective of the host galaxies of binary compact objects offers a complementary approach, not only shedding light on the physical conditions that favor different formation channels but also enhancing our ability to interpret GW observations. In this talk, I will discuss two different approaches to modeling the host galaxies of binary compact objects: one based on population synthesis models combined with galaxy catalogs from cosmological simulations, and another based on empirical galaxy scaling relations. I will highlight some of the key results from these models and discuss the next steps where host galaxy properties can provide critical constraints on the origin and evolution of compact object binaries.

Zoom link: https://pitp.zoom.us/j/98089871850

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

The classical rainbow cycle conjecture of Keevash, Mubayi, Verstrate, and Sudakov says that every properly edge-colored graph of average degree \Omega(log n) contains a "rainbow" cycle, i.e., a cycle with edges of all distinct colors. Recent advances have almost resolved this conjecture up to an additional log log n factor.  

In this talk, I will describe hypergraph variants of the graph rainbow problem and show how they are intimately related to the existence of (linear) locally decodable and locally correctable codes. 
I will then describe the "Kikuchi Matrix Method" to solve such problems - a general principle that converts hypergraph rainbow problems into related graph counterparts. Consequently, we obtain an exponential lower bound on linear 3 query locally correctable codes, a cubic lower bound on 3 query locally decodable codes (LDCs) and more generally, $k^{q/(q-2)}$ lower bound for all $q$-query LDCs. The case of even $q$ was known since 2004, but the best known bounds for odd q$ were obtained by treating a $q$ query code as a $q+1$ query code instead. 

For those familiar with the work in this area, this will be a combinatorial viewpoint on the spectral methods that yield similar results when the code is restricted to be linear. 

Based on joint works with Omar Alrabiah, Arpon Basu, David Munha-Correia, Venkat Guruswami, Tim Hsieh, Peter Manohar, Sidhanth Mohanty, Andrew Lin, and Benny Sudakov

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 

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of O(1/ϵ). In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs.

Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS'95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a "local-to-global" phenomenon for (a slight strengthening of) the generalized Singleton bound.

As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.

Based on joint work with Fernando Granha Jeronimo, Tushant Mittal, and Shashank Srivastava.