Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR26-204 | 22nd September 2026
Mitali Bafna, Anqi Li, Quynh Nguyen

Good Quantum Locally Testable Codes from Product Expansion

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas (2026) about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick (2024) for constructing quantum LTCs, instantiated with ... more >>>


TR26-203 | 22nd September 2026
Ben Lee Volk

Improved Algorithms for the Remote Point Problem

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the ... more >>>


TR26-202 | 21st September 2026
Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders.
In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev.
more >>>



Next next


ISSN 1433-8092 | Imprint