5 citations · 10 across the 10 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
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…