10 citations · 63 across the 24 of their papers we have counts for
21 papers · 1 filter
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…
Explicit SoS lower bounds from high-dimensional expanders
Irit Dinur, Yuval Filmus, Prahladh Harsha +1
We construct an explicit family of 3XOR instances which is hard for levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a…
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…