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

__
TR23-043
| 9th April 2023
__

Yotam Dikstein, Irit Dinur#### Coboundary and cosystolic expansion without dependence on dimension or degree

__
TR20-072
| 5th May 2020
__

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi#### Locally testable codes via high-dimensional expanders

__
TR19-112
| 1st September 2019
__

Yotam Dikstein, Irit Dinur#### Agreement testing theorems on layered set systems

__
TR18-075
| 23rd April 2018
__

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha#### Boolean function analysis on high-dimensional expanders

Revisions: 3

Yotam Dikstein, Irit Dinur

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

Yotam Dikstein, Irit Dinur

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

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

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

Yotam Dikstein, Irit Dinur

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

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

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