Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HIGH DIMENSIONAL EXPANDERS:
Reports tagged with high dimensional expanders:
TR18-075 | 23rd April 2018
Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

Boolean function analysis on high-dimensional expanders

Revisions: 2

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>


TR18-134 | 24th July 2018
Tali Kaufman, David Mass

Cosystolic Expanders over any Abelian Group

In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>>


TR19-112 | 1st September 2019
Yotam Dikstein, Irit Dinur

Agreement testing theorems on layered set systems

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 ... more >>>


TR19-124 | 28th August 2019
Roy Gotlib, Tali Kaufman

Testing Odd Direct Sums Using High Dimensional Expanders

In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.
Interestingly, our work ... more >>>




ISSN 1433-8092 | Imprint