Search Talks

I will present a method to reduce extremal combinatorial problems to establishing the unsatisfiability of k-sparse linear equations mod 2 (aka k-XOR formulas) with a limited amount of randomness. This latter task is then accomplished by bounding the spectral norm of certain "Kikuchi" matrices built from the k-XOR formulas. In these talks, I will discuss a couple of applications of this method from the following list. 

1. Proving hypergraph Moore bound (Feige's 2008 conjecture) -- the optimal trade-off between the number of equations in a system of k-sparse linear equations modulo 2 and the size of the smallest linear dependent subset. This theorem generalizes the famous irregular Moore bound of Alon, Hoory and Linial (2002) for graphs (equivalently, 2-sparse linear equations mod 2).

2. Proving a cubic lower bound on 3-query locally decodable codes (LDCs), improving on a quadratic lower bound of Kerenedis and de Wolf (2004) and its generalization to q-query locally decodable codes for all odd q,  

 3. Proving an exponential lower bound on linear 3-query locally correctable codes (LCCs). This result establishes a sharp separation between 3-query LCCs and 3-query LDCs that are known to admit a construction with a sub-exponential length. It is also the first result to obtain any super-polynomial lower bound for >2-query local codes. 

Time permitting, I may also discuss applications to strengthening Szemeredi's theorem, which asks for establishing the minimal size of a random subset of integers S such that every dense subset of integers contains a 3-term arithmetic progression with a common difference from S, and the resolution of Hamada's 1970 conjecture on the algebraic rank of binary 4-designs. 

I will include pointers to the many open questions and directions where meaningful progress seems within reach for researchers who may get interested in some of the topics.  

I will present a method to reduce extremal combinatorial problems to establishing the unsatisfiability of k-sparse linear equations mod 2 (aka k-XOR formulas) with a limited amount of randomness. This latter task is then accomplished by bounding the spectral norm of certain "Kikuchi" matrices built from the k-XOR formulas. In these talks, I will discuss a couple of applications of this method from the following list. 

1. Proving hypergraph Moore bound (Feige's 2008 conjecture) -- the optimal trade-off between the number of equations in a system of k-sparse linear equations modulo 2 and the size of the smallest linear dependent subset. This theorem generalizes the famous irregular Moore bound of Alon, Hoory and Linial (2002) for graphs (equivalently, 2-sparse linear equations mod 2).

2. Proving a cubic lower bound on 3-query locally decodable codes (LDCs), improving on a quadratic lower bound of Kerenedis and de Wolf (2004) and its generalization to q-query locally decodable codes for all odd q,  

 3. Proving an exponential lower bound on linear 3-query locally correctable codes (LCCs). This result establishes a sharp separation between 3-query LCCs and 3-query LDCs that are known to admit a construction with a sub-exponential length. It is also the first result to obtain any super-polynomial lower bound for >2-query local codes. 

Time permitting, I may also discuss applications to strengthening Szemeredi's theorem, which asks for establishing the minimal size of a random subset of integers S such that every dense subset of integers contains a 3-term arithmetic progression with a common difference from S, and the resolution of Hamada's 1970 conjecture on the algebraic rank of binary 4-designs. 

I will include pointers to the many open questions and directions where meaningful progress seems within reach for researchers who may get interested in some of the topics.  

In this talk, we will look at a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime.

Based on an upcoming joint work with Sourya Roy, University of Iowa.

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.