License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24133
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2413/
Go to the corresponding Portal |
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 error-correcting 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 well-known that the nearest codeword problem is NP-hard. 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) de-randomizing 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 r-far 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 = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2413},
annote = {Keywords: }
}
Collection: |
|
09421 - Algebraic Methods in Computational Complexity |
Issue Date: |
|
2010 |
Date of publication: |
|
19.01.2010 |