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:

TR23-119 | 18th August 2023
Yotam Dikstein, Irit Dinur

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Given a family X of subsets of [n] and an ensemble of local functions $\{f_s:s\to\Sigma \;|\; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. For example, the V-test chooses ... more >>>

TR23-043 | 9th April 2023
Yotam Dikstein, Irit Dinur

Coboundary and cosystolic expansion without dependence on dimension or degree

We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and ... more >>>

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
Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

Boolean function analysis on high-dimensional expanders

Revisions: 3

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