High dimensional expanders imply agreement expanders

by Irit Dinur and Tali Kaufman

Oded's comments

This is the third (and hopefully last...) time that I'm forced to choose a work that is dedicated to my 60th birthday (see prior choices 216 and 219). The sweetness of the authors' gesture is reduced by the fact that they proved me wrong: In a number of occasions, in the last couple of years, I told Tali and Irit that I don't believe that the study of high dimensional expanders would yield a result that I would consider interesting for the theory of computation (ToC). Needless to say, a derandomized direct product test with an optimal (i.e., linear) number of sets is interesting for ToC.

A direct product test is a collection $C=(S_1,...,S_m)$ of small (i.e., constant) size subsets of $[n]$ (i.e., $c=|S_i|$ for all $i$) such that:

  1. Random subsets in $C$ have good sampling features (e.g., they hit any constant density subset of $[n]$ with probability the tends to zero with $c$).
  2. There is a 2-query tester for the set of direct product functions defined over $C$, where a function $F:C\to\Sigma^c$ is a direct product function if there exists a function $f:[n]\to\Sigma$ such that for every $S=(e_1,....,e_c)$ in $C$ it holds that $F(S)=(f(e_1),...,f(e_c))$.
The fact that the collection of all $c$-subsets constitutes a direct product test as well as explicit constructions of such collections of size $\poly(n)$, where the polynomail is independent of $c$, have been known for two decades (see HERE). But obtaining linear size collections seemed almost impossible. For starters, the sampling condition implies that typical elements can only occur in a constant number of subsets, and so most vertices in the graph describing the 2-query test must have constant degree. Note, however, that a random collection of this type is unlikely to yield a good 2-query test, since the two queries will typically intersect in one element only (and an assignment of a wrong value to a single random element in each $c$-subset will be detected with probability approximately $1/c$).

The original abstract

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is *linear* in the size of the universe.

Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree tests such as line vs. line and plane vs. plane.

For a generic hypergraph, we introduce the notion of agreement expansion, which captures the usefulness of the hypergraph for an agreement test. We show that explicit bounded degree agreement expanders exist, based on Ramanujan complexes.

See ECCC TR17-089.

Back to list of Oded's choices.