HDX condensers
I Cohen, R Roth, A Ta-Shma - 2023 IEEE 64th Annual …, 2023 - ieeexplore.ieee.org
More than twenty years ago, Capalbo, Rein-gold, Vadhan and Wigderson gave the first (and
up to date only) explicit construction of a bipartite expander with almost full combinatorial …
up to date only) explicit construction of a bipartite expander with almost full combinatorial …
Asymptotically-Good RLCCs with (log n)^(2+ o (1)) Queries
G Cohen, T Yankovitz - 39th Computational Complexity …, 2024 - drops.dagstuhl.de
Abstract Recently, Kumar and Mon reached a significant milestone by constructing
asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query …
asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query …
Simple constructions of unique neighbor expanders from error-correcting codes
In this note, we give very simple constructions of unique neighbor expander graphs starting
from spectral or combinatorial expander graphs of mild expansion. These constructions and …
from spectral or combinatorial expander graphs of mild expansion. These constructions and …
Bipartite Unique Neighbour Expanders via Ramanujan Graphs
R Asherov, I Dinur - Entropy, 2024 - mdpi.com
We construct an infinite family of bounded-degree bipartite unique neighbour expander
graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders …
graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders …
When Can an Expander Code Correct Ω (n) Errors in O (n) Time?
K Cheng, M Ouyang, C Shangguan… - Approximation …, 2024 - drops.dagstuhl.de
Tanner codes are graph-based linear codes whose parity-check matrices can be
characterized by a bipartite graph G together with a linear inner code C₀. Expander codes …
characterized by a bipartite graph G together with a linear inner code C₀. Expander codes …
Non-commutative error correcting codes and proper subgroup testing
M Chapman, I Dinur, A Lubotzky - arXiv preprint arXiv:2406.17372, 2024 - arxiv.org
Property testing has been a major area of research in computer science in the last three
decades. By property testing we refer to an ensemble of problems, results and algorithms …
decades. By property testing we refer to an ensemble of problems, results and algorithms …
Two-Sided Lossless Expanders in the Unbalanced Setting
We present the first explicit construction of two-sided lossless expanders in the unbalanced
setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our …
setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our …