Yotam Dikstein

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2026

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…

cs.CC2024

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 $X$ be a $k$ -dimensional HDX. We show for any $i \leq k$ and $f:X(i)\to [0,1]…

cs.CC2024

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…

cs.CC2024

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Yotam Dikstein, Irit Dinur

Given a family $X$ of subsets of $[n]$ and an ensemble of local functions ${f_{s} : s \to I^£ ∣ s \in X}$ , an agreement test is a randomized property tester that is supposed to test…