# Deterministic approximation algorithms for the nearest codeword problem

Noga Alon, Rina Panigrahy, Sergey Yekhanin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations

## 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) Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings 339-351 13 https://doi.org/10.1007/978-3-642-03685-9_26 Published - 2009 Yes 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 StatesDuration: 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) 5687 LNCS 0302-9743 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 United States Berkeley, CA 8/21/09 → 8/23/09

## All Science Journal Classification (ASJC) codes

• Theoretical Computer Science
• General Computer Science

## Fingerprint

Dive into the research topics of 'Deterministic approximation algorithms for the nearest codeword problem'. Together they form a unique fingerprint.