Name
Abstract | ||
|---|---|---|
The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v2 Fn 2 and a linear space L Fn 2 of dimension k NCP asks to find a point l2 L that minimizes the (Hamming) distance from v: It is well-known that the nearest codeword problem is NP-hard. Therefore ap- proximation algorithms are of interest. The best efficient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio ofO(k=c) for an arbitrary constantc; and a randomized algorithm that achieves an approximation ratio ofO(k= logn): In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work. Specifically, we obtain: A polynomial timeO(n= logn)-approximation algorithm; An nO(s) time O(k log(s)n= logn)-approximation algorithm, where log(s)n stands for s iterations of log; e.g., log(2)n = log logn; AnnO(log n) timeO(k= logn)-approximation algorithm. We also initiate a study of the following Remote Point Problem (RPP). Given a linear spaceL Fn 2 of dimen- sion k RPP asks to find a point v 2 Fn 2 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 ( n logk=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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03685-9_26 | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
nearest codeword problem,time o,deterministic algorithm,approximation ratio,approximation algorithm,dimension k rpp,deterministic polynomial time algorithm,k log,linear space,deterministic approximation algorithms,dimension k ncp,randomized algorithm,hamming distance,computational complexity,polynomial time,lower bound,error correction code | Approximation algorithm,Hamming code,Discrete mathematics,Randomized algorithm,Combinatorics,Linear space,Linear code,Deterministic algorithm,Time complexity,Mathematics,Computational complexity theory | Conference |
Volume | Issue | ISSN |
15 | 065 | 0302-9743 |
Citations | PageRank | References |
19 | 0.83 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Rina Panigrahy | 2 | 3203 | 269.05 |
| Sergey Yekhanin | 3 | 983 | 52.33 |