Publications

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product testing, also known as agreement testing, is the following problem. Let X be a family of k-element subsets of [n] and let {fs:s→Σ}s∈X be an ensemble of local functions, each defined over a subset

s⊂[n]. Suppose that we run the following so-called agreement test: choose a random pair of sets s1,s2∈X that intersect on √k elements, and accept if fs1,fs2 agree on the elements in s1∩s2. We denote the success probability of this test by Agr({fs}). Given that Agr({fs})=ϵ>0, is there a global function G:[n]→Σ such that fs=G|s for a non-negligible fraction of s∈X?

We construct a family X of k-subsets of [n] such that |X|=O(n) and such that it satisfies the low acceptance agreement theorem. Namely, Agr({fs})>ϵ⟶ there is a function G:[n]→Σ such that Prs[fs≈0.99G|s]≥poly(ϵ).

A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family X is just the k-faces of the new symplectic HDXs. The later serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. 

We introduce and study swap cosystolic expansion, a new expansion property of simplicial complexes. We prove lower bounds for swap coboundary expansion of spherical buildings and use them to lower bound swap cosystolic expansion of the LSV Ramanujan complexes. Our motivation is the recent work (in a companion paper) showing that swap cosystolic expansion implies agreement theorems. Together the two works show that these complexes support agreement tests in the low acceptance regime.

Swap cosystolic expansion is defined by considering, for a given complex X, its faces complex F^rX, whose vertices are r-faces of X and where two vertices are connected if their disjoint union is also a face in

X. The faces complex F^rX is a derandomizetion of the product of X with itself r times. The graph underlying

F^rX is the swap walk of X, known to have excellent spectral expansion. The swap cosystolic expansion of X

is defined to be the cosystolic expansion of F^rX.

Our main result is a exp(−O(√r)) lower bound on the swap coboundary expansion of the spherical building and the swap cosystolic expansion of the LSV complexes. For more general coboundary expanders we show a weaker lower bound of

exp(−O(r)). 

We point out an error in the paper "Linear Time Encoding of LDPC Codes" (by Jin Lu and José M. F. Moura, IEEE Trans). The paper claims to present a linear time encoding algorithm for every LDPC code. We present a family of counterexamples, and point out where the analysis fails. The algorithm in the aforementioned paper fails to encode our counterexample, let alone in linear time. 

Given a family X of subsets of [n] and an ensemble of local functions {fs:s→Σ|s∈X}, an agreement test is a randomized property tester that is supposed to test whether there is some global function G:[n]→Σ such that

fs=G|s for many sets s. A "classical" small-soundness agreement theorem is a list-decoding

(LD) statement, saying that

Agree({fs})>ε⟹∃G1,…,Gℓ, Ps[fs≈0.99Gi|s]≥poly(ε),i=1,…,ℓ.        (LD)

Such a statement is motivated by PCP questions and has been shown in the case where X=([n]^k), or where

X is a collection of low dimensional subspaces of a vector space. In this work we study small the case of on high dimensional expanders X. It has been an open challenge to analyze their small soundness behavior. Surprisingly, the small soundness behavior turns out to be governed by the topological covers of X .We show that:

1. If X has no connected covers, then (LD) holds, provided that X satisfies an additional expansion property.

2. If X has a connected cover, then (LD) necessarily fails.

3. If X has a connected cover (and assuming the additional expansion property), we replace the (LD) by a weaker statement we call lift-decoding:

Agree({ fs})>ε⟹∃ cover ρ:Y↠X, and G:Y(0)→Σ, such that 

(LFD) Ps~↠s[fs≈0.99G|s~]≥poly(ε), where s~↠s means that ρ(s~)=s.

The additional expansion property is cosystolic expansion of a complex derived from X holds for the spherical building and for quotients of the Bruhat-Tits building. 

We prove new lower bounds on the cosystolic expansion of several families of high dimensional expanders, and on the coboundary expansion of the order complexes of geometric lattices, including the spherical building of SL_n(F_q). The lower bounds hold for high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and by Kaufman and Oppenheim.

Our bounds are absolute constants that do not depend on the degree of the complex nor on its dimension, a feature that may be important for applications such as cover stability and agreement testing. In comparison, existing bounds decay exponentially with the dimension (for spherical buildings) and in addition decay linearly with the degree (for all known bounded-degree high dimensional expanders). Our results are based on several new techniques:

– We develop a new “color-restriction” technique which enables proving dimension-free expansion by restricting a multi-partite complex to small random subsets of its color classes.

– We introduce a degree-independent local-correction algorithm that starts with a small-coboundary chain, and finds a nearby cocycle.

– We derive absolute bounds on the coboundary expansion of the spherical building (and any order complex of a geometric lattice) by constructing a novel family of very short cones.

Connect two copies of a given graph G by a perfect matching. What are the properties of the graphs obtained by recursively repeating this procedure? We show that this construction shares some of the structural properties of the hypercube, such as a simple routing scheme and small edge expansion. However, when the matchings are uniformly random, the resultant graph also has similarities with a random regular graph, including: a smaller diameter and better vertex expansion than the hypercube; a semicircle law for its eigenvalues; and no non-trivial automorphisms. We propose a simple deterministic matching which we believe could provide a derandomization.

Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are "far" from all codewords by probing a given word only at a very few (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries.

In this paper, we present a new approach towards constructing such LTCs using the machinery of high-dimensional expanders. To this end, we consider the Tanner representation of a code, which is specified by a graph and a base code. Informally, our result states that if this graph is part of a high-dimensional expander then the local testability of the code follows from the local testability of the base code.

This work unifies and generalizes the known results on testability of the Hadamard, Reed-Muller and lifted codes on the Subspace Complex, all of which are proved via local self correction. However, unlike previous results, constant rounds of self correction do not suffice as the diameter of the underlying test graph can be logarithmically large in a high-dimensional expander and not constant as in all known earlier results. We overcome this technical hurdle by performing iterative self correction with logarithmically many rounds and tightly controlling the error in each iteration using properties of the high-dimensional expander.

Given this result, the missing ingredient towards constructing a constant-query LTC with positive rate and constant relative distance is an instantiation of a base code that interacts well with a constant-degree high-dimensional expander. 

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test. Previous work has shown that high dimensional expansion is useful for agreement tests. We extend these results to more general families of subsets, beyond simplicial complexes. These include

- Agreement tests for set systems whose sets are faces of high dimensional expanders. Our new tests apply to all dimensions of complexes both in case of two-sided expansion and in the case of one-sided partite expansion. This improves and extends an earlier work of Dinur and Kaufman (FOCS 2017) and applies to matroids, and potentially many additional complexes.

- Agreement tests for set systems whose sets are neighborhoods of vertices in a high dimensional expander. This family resembles the expander neighborhood family used in the gap-amplification proof of the PCP theorem. This set system is quite natural yet does not sit in a simplicial complex, and demonstrates some versatility in our proof technique.

- Agreement tests on families of subspaces (also known as the Grassmann poset). This extends the classical low degree agreement tests beyond the setting of low degree polynomials.

Our analysis relies on a new random walk on simplicial complexes which we call the ``complement random walk'' and which may be of independent interest. This random walk generalizes the non-lazy random walk on a graph to higher dimensions, and has significantly better expansion than previously-studied random walks on simplicial complexes. 

We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analog of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analog is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. Our random-walk definition and the decomposition have the additional advantage that they extend to the more general setting of posets, encompassing both high-dimensional expanders and the Grassmann poset, which appears in recent work on the unique games conjecture.

We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a constant-degree high-dimensional expander can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing only |X(k−1)|=O(n) points in contrast to n-choose-k points in the k-slice (which consists of all n-bit strings with exactly k ones).