Alon, Noga ;
Panigrahy, Rina ;
Yekhanin, Sergey
Deterministic approximation algorithms for the nearest codeword problem
Abstract
The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of errorcorrecting codes. Given a point v in F_2^n and a linear space L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance from v.
It is wellknown that the nearest codeword problem is NPhard. Therefore approximation algorithms are of interest. The best effcient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a
deterministic algorithm that achieves an approximation ratio of O(k/c)
for an arbitrary constant c; and a randomized algorithm that achieves
an approximation ratio of O(k/ log n).
In this paper we present new deterministic algorithms for approximating
the NCP that improve substantially upon the earlier work, (almost) derandomizing the randomized algorithm of Berman and Karpinski.
We also initiate a study of the following Remote Point Problem (RPP). Given a linear space L in F_2^n of dimension k RPP asks to find a point v in F_2^n that is far from L. We say that an algorithm achieves a remoteness of r for the RPP if it always outputs a point v that is at least rfar from L. In this paper we present a deterministic polynomial time algorithm that achieves a remoteness of Omega(n log k / k) for all k < n/2.
We motivate the remote point problem by relating it to both the nearest codeword problem and the matrix rigidity approach to circuit lower bounds in
computational complexity theory.
BibTeX  Entry
@InProceedings{alon_et_al:DSP:2010:2413,
author = {Noga Alon and Rina Panigrahy and Sergey Yekhanin},
title = {Deterministic approximation algorithms for the nearest codeword problem},
booktitle = {Algebraic Methods in Computational Complexity},
year = {2010},
editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
number = {09421},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2413},
annote = {Keywords: }
}
2010
Seminar: 

09421  Algebraic Methods in Computational Complexity

Issue date: 

2010 
Date of publication: 

2010 