5 citations · 10 across the 10 of their papers we have counts for
15 papers
High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Russell Impagliazzo +1
We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a co…
Sparser Abelian High Dimensional Expanders
Yotam Dikstein, Siqi Liu, Avi Wigderson
We present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group . Our expansion proofs use only linear algebra and comb…
Conditional Non-Soficity of p-adic Deligne Extensions: on a Theorem of Gohla and Thom
Michael Chapman, Yotam Dikstein, Alexander Lubotzky
A long standing problem asks whether every group is sofic, i.e., can be separated by almost-homomorphisms to the symmetric group . Similar problems have been asked with res…
Sparse High Dimensional Expanders via Local Lifts
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. L…
Chernoff Bounds and Reverse Hypercontractivity on HDX
Yotam Dikstein, Max Hopkins
We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let be a -dimensional HDX. We show for any and $f:X(i)\to [0,1]…
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
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…
The linear time encoding scheme fails to encode
Yotam Dikstein, Irit Dinur, Shiri Sivan
We point out an error in the paper "Linear Time Encoding of LDPC Codes" (by Jin Lu and José M. F. Moura, IEEE Trans). The paper claims to present a linear time encoding algorithm f…
Swap cosystolic expansion
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 u…
Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
Yotam Dikstein, Irit Dinur
Given a family of subsets of and an ensemble of local functions , an agreement test is a randomized property tester that is supposed to test…
Coboundary and cosystolic expansion without dependence on dimension or degree
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 homog…
New High Dimensional Expanders from Covers
Yotam Dikstein
We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander…
Randomly twisted hypercubes -- between structure and randomness
Itai Benjamini, Yotam Dikstein, Renan Gross +1
Twisted hypercubes are generalizations of the Boolean hypercube, obtained by iteratively connecting two instances of a graph by a uniformly random perfect matching. Dudek et al. sh…
Locally testable codes via high-dimensional expanders
Yotam Dikstein, Irit Dinur, Prahladh Harsha +1
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 giv…
Agreement testing theorems on layered set systems
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 testi…
Boolean functions on high-dimensional expanders
Yotam Dikstein, Irit Dinur, Yuval Filmus +1
We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the ear…