Deterministic approximation algorithms for the nearest codeword problem

Noga Alon, Rina Panigrahy, Sergey Yekhanin

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

21 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 languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages339-351
Number of pages13
DOIs
StatePublished - 2009
Event12th 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 2009Aug 23 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5687 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
CountryUnited States
CityBerkeley, CA
Period8/21/098/23/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this