Talks

Expanders are well-connected graphs that have been extensively studied and have numerous applications in computer science, including error-correcting codes. High-dimensional expanders (HDXs) generalize expanders to hypergraphs and have the powerful local-to-global property. Roughly speaking, this property states that the expansion of an HDX can be certified by the expansion of certain local structures. This property has made HDXs crucial in the recent breakthrough on locally testable codes (LTCs) [Dinur et al.'22]. These LTCs simultaneously achieve constant rate, constant relative distance, and constant query complexity. However, despite these desirable properties, these LTCs have yet to find applications in proof systems, as they lack the crucial multiplication property present in widely used polynomial codes. A major open question is: Do there exist LTCs with the multiplication property that achieve the same rate, distance, and query complexity as those constructed by Dinur et al.?

In this talk, I will provide intuition behind the connection between HDXs and LTCs, explain why the LTCs by Dinur et al. lack the multiplication property, and discuss my recent and ongoing work on constructing LTCs with the multiplication property. This talk is based on joint work with Irit Dinur, Huy Tuan Pham, and Rachel Zhang.

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