## Abstract

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v ∈ double-struck F _{2} ^{n} and a linear space L ⊆ double-struck F _{2} ^{n} of dimension k NCP asks to find a point l ∈ 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 efficient 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. Specifically, we obtain: A polynomial time O(n/logn)-approximation algorithm; An n ^{O(s)} time O(k log ^{(s)} n/log n)-approximation algorithm, where log ^{(s)} n stands for s iterations of log, e.g., log ^{(2)} n=log log n; An n ^{O(log* n)} time O(k/log n)-approximation algorithm. We also initiate a study of the following Remote Point Problem (RPP). Given a linear space L ⊆ double-struck F _{2} ^{n} of dimension k RPP asks to find a point v ∈ double-struck 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 Ω(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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings |

Pages | 339-351 |

Number of pages | 13 |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

Event | 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States Duration: Aug 21 2009 → Aug 23 2009 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5687 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 |
---|---|

Country/Territory | United States |

City | Berkeley, CA |

Period | 8/21/09 → 8/23/09 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science