ECCC-Report TR12-149https://eccc.weizmann.ac.il/report/2012/149Comments and Revisions published for TR12-149en-usFri, 09 Nov 2012 00:41:23 +0200
Comment 1
| This version |
Madhu Sudan
https://eccc.weizmann.ac.il/report/2012/149#comment1This paper subsumes a previous paper by the first and third authors with the same title,
ECCC TR12-106. This version includes (in addition to a new author) bounds on the sizes of Nikodym sets.Fri, 09 Nov 2012 00:41:23 +0200https://eccc.weizmann.ac.il/report/2012/149#comment1
Paper TR12-149
| New affine-invariant codes from lifting |
Alan Guo,
Swastik Kopparty,
Madhu Sudan
https://eccc.weizmann.ac.il/report/2012/149In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension and lifts them to higher
dimensions by requiring their restriction to every subspace of
the original dimension to be a codeword of the code being lifted.
While the operation is of interest on its own, this work focusses
on new ranges of parameters that can be obtained by such codes,
in the context of local correction and testing.
In particular we present four interesting ranges of parameters that
can be achieved by such lifts, all of which are new in the context
of affine-invariance and some may be new even in general.
The main highlight is a construction of high-rate codes
with sublinear time decoding. The only prior construction of such
codes is due to Kopparty, Saraf and Yekhanin~\cite{KSY}.
All our codes are extremely simple, being just lifts of various
parity check codes (codes with one symbol of redundancy), and
in the final case, the lift of a Reed-Solomon code.
We also present a simple connection between certain lifted codes
and lower bounds on the size of ``Nikodym sets''. Roughly, a Nikodym set
in $\mathbb{F}_q^m$ is a set $S$ with the property that every point has a line
passing through it which is almost entirely contained in $S$. While
previous lower bounds on Nikodym sets were roughly growing as
$q^m/2^m$, we use our lifted codes to prove a lower bound of $(1 - o(1))q^m$
for fields of constant characteristic.Thu, 08 Nov 2012 19:34:54 +0200https://eccc.weizmann.ac.il/report/2012/149