Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yotam Dikstein:

TR20-072 | 5th May 2020
Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

Locally testable codes via high-dimensional expanders

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 small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. ... 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 >>>

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

ISSN 1433-8092 | Imprint