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