Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HADAMARD CODES:
TR08-020 | 7th March 2008
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

#### Decodability of Group Homomorphisms beyond the Johnson Bound

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

#### Erasures versus Errors in Local Decoding and Property Testing

Revisions: 1

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

ISSN 1433-8092 | Imprint