Asymptotically good quantum and locally testable classical LDPC codes
P Panteleev, G Kalachev - Proceedings of the 54th Annual ACM SIGACT …, 2022 - dl.acm.org
We study classical and quantum LDPC codes of constant rate obtained by the lifted product
construction over non-abelian groups. We show that the obtained families of quantum LDPC …
construction over non-abelian groups. We show that the obtained families of quantum LDPC …
Near-linear time decoding of ta-shma's codes via splittable regularity
FG Jeronimo, S Srivastava, M Tulsiani - … of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes
of distance 1/2− є/2 and rate Ω (є2). In a breakthrough result, Ta-Shma [STOC 2017] …
of distance 1/2− є/2 and rate Ω (є2). In a breakthrough result, Ta-Shma [STOC 2017] …
Hypercontractivity on high dimensional expanders
Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally
studied over the discrete hypercube, recent years have seen increasing interest in …
studied over the discrete hypercube, recent years have seen increasing interest in …
Hypercontractivity on high dimensional expanders
We prove hypercontractive inequalities on high dimensional expanders. As in the settings of
the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities …
the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities …
No where to go but high: A perspective on high dimensional expanders
R Gotlib, T Kaufman - arXiv preprint arXiv:2304.10106, 2023 - arxiv.org
" No Where to go but in" is a well known statement of Osho. Osho meant to say that the
answers to all our questions should be obtained by looking into ourselves. In a paraphrase …
answers to all our questions should be obtained by looking into ourselves. In a paraphrase …
High dimensional expanders: Eigenstripping, pseudorandomness, and unique games
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen
an incredible amount of study and application since their introduction by Kaufman and Mass …
an incredible amount of study and application since their introduction by Kaufman and Mass …
New Codes on High Dimensional Expanders
I Dinur, S Liu, RY Zhang - arXiv preprint arXiv:2308.15563, 2023 - arxiv.org
We describe a new parameterized family of symmetric error-correcting codes with low-
density parity-check matrices (LDPC). Our codes can be described in two seemingly …
density parity-check matrices (LDPC). Our codes can be described in two seemingly …
List agreement expansion from coboundary expansion
R Gotlib, T Kaufman - arXiv preprint arXiv:2210.15714, 2022 - arxiv.org
One of the key components in PCP constructions are agreement tests. In agreement test the
tester is given access to subsets of fixed size of some set, each equipped with an …
tester is given access to subsets of fixed size of some set, each equipped with an …
From Grassmannian to Simplicial High-Dimensional Expanders
L Golowich - 2023 IEEE 64th Annual Symposium on …, 2023 - ieeexplore.ieee.org
In this paper, we present a new construction of simplicial complexes of subpolynomial
degree with arbitrarily good local spectral expansion. Previously, the only known high …
degree with arbitrarily good local spectral expansion. Previously, the only known high …
[PDF][PDF] High-probability list-recovery, and applications to heavy hitters
D Doron, M Wootters - Leibniz international proceedings in informatics, 2022 - par.nsf.gov
An error correcting code C: Σk→ Σn is efficiently list-recoverable from input list size ℓ if for
any sets L1,..., Ln⊆ Σ of size at most ℓ, one can efficiently recover the list L={x∈ Σk:∀ j∈[n] …
any sets L1,..., Ln⊆ Σ of size at most ℓ, one can efficiently recover the list L={x∈ Σk:∀ j∈[n] …