Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ERROR-CORECTING CODES:
Reports tagged with error-corecting codes:
TR11-165 | 8th December 2011
Elena Grigorescu, Chris Peikert

List Decoding Barnes-Wall Lattices

Revisions: 2

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>


TR19-090 | 27th June 2019
Ronen Shaltiel, Swastik Kopparty, Jad Silbak

Quasilinear time list-decodable codes for space bounded channels

Revisions: 2

We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>


TR25-146 | 15th October 2025
Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang

From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids

In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent work Levi, Mosheiff, and Shagrithaya (FOCS 2025) gave a novel unified framework for calculating the threshold rates of local properties for random ... more >>>




ISSN 1433-8092 | Imprint