Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SELF CORRECTION:
Reports tagged with self correction:
TR10-067 | 14th April 2010
Sourav Chakraborty, Eldar Fischer, Arie Matsliah

#### Query Complexity Lower Bounds for Reconstruction of Codes

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>

ISSN 1433-8092 | Imprint