All reports by Author Yotam Dikstein:

__
TR24-102
| 29th May 2024
__

Inbar Ben Yaacov, Yotam Dikstein, Gal Maor#### Sparse High Dimensional Expanders via Local Lifts

Revisions: 1

__
TR24-082
| 17th April 2024
__

Yotam Dikstein, Max Hopkins#### Chernoff Bounds and Reverse Hypercontractivity on HDX

Revisions: 1

__
TR24-019
| 2nd February 2024
__

Yotam Dikstein, Irit Dinur, Alexander Lubotzky#### Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Revisions: 1

__
TR23-209
| 23rd December 2023
__

Yotam Dikstein, Irit Dinur#### Swap cosystolic expansion

Revisions: 1

__
TR23-119
| 18th August 2023
__

Yotam Dikstein, Irit Dinur#### Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Revisions: 1

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

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

Revisions: 4

Inbar Ben Yaacov, Yotam Dikstein, Gal Maor

High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex ... more >>>

Yotam Dikstein, Max Hopkins

We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let $X$ be a $k$-dimensional HDX. We show for any $i \leq k$ and function $f: X(i) \to [0,1]$:

\[

\Pr_{s \in X(k)}\left[\left|\underset{{t \subseteq s}}{\mathbb{E}}[f(t)] - \mu \right| \geq \varepsilon \right] \leq \exp\left(-\varepsilon^2 \frac{k}{i}\right).

\]

Using ...
more >>>

Yotam Dikstein, Irit Dinur, Alexander Lubotzky

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product ... more >>>

Yotam Dikstein, Irit Dinur

We introduce and study swap cosystolic expansion, a new expansion property of simplicial complexes. We prove lower bounds for swap coboundary expansion of spherical buildings and use them to lower bound swap cosystolic expansion of the LSV Ramanujan complexes. Our motivation is the recent work (in a companion paper) showing ... more >>>

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

Irit Dinur, Yotam Dikstein, 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 >>>