Very Local Self Correcting of Homomorphism and MPC Codes
Speaker: Adi Akavia , IAS/DIMACS
Date: December 5 2008
Time: 10:30AM to 12:00PM
Location: 32-G449
Contact: be, 3-6098, imbe@mit.edu
Relevant URL:
Blum-Luby-Rubinfeld gave a local self correcting algorithm for
homomorphism codes Hom(G,H) for any finite abelian groups G and H. The
BLR algorithm, given an entry location s and oracle access to a
corrupted codeword w close to a codeword C, outputs the value of C on
entry s, while reading only a constant number of entries in
w. Although the number of *entries* read by the BLR algorithm is
constant, the number of read *bits* is O(log|H|), as each alphabet
symbol is represented by log|H| bits. This number of read bits may be
quite large with respect to the information rate; in particular, for
Hom(Z_N,Z_N) the number of read bits is larger than the information
rate.
In this work we present a local self correcting algorithm for
homomorphism codes Hom(Z_N^k,Z_N) that reads O(k) *bits* to output a
single bit of the value of the closest codeword on the given entry (in
a non standard binary representation); the algorithm is restricted to
codewords C and entries s corresponding to invertible group elements,
and extends to other codes Hom(G,H). Our algorithm improves over prior
works as long as k = o(log N). In particular, for Hom(Z_N,Z_N) our
algorithm reduces the number of read bits from O(log N) to O(1).
In addition, we use our algorithm to obtain the first local self
correcting algorithm for the MPC codes of Akavia-Goldwasser-Safra
FOCS'03, and for their generalizations defined here.
In terms of techniques, we develop a new approach for local self
correcting in which we first reduce the self correcting problem into a
property testing problem concerning the location of significant
Fourier transform coefficients (aka, SFT-testing), and then give an
efficient algorithm solving SFT-testing with O(k) read bits. The
SFT-testing algorithm may be of independent interest.
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in December 2008
