# Deterministic Approximation Algorithms for the Nearest Codeword Problem

Noga Alon, Rina Panigrahy, Sergey Yekhanin

Research output: Contribution to journalConference articlepeer-review

## Abstract

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v Fn2 and a linear space L Fn2 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/ log n)-approximation algorithm; – An nO(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 nO(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 Fn2 of dimension k RPP asks to find a point v Fn2 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) Dagstuhl Seminar Proceedings 9421 Published - 2010 Yes Algebraic Methods in Computational Complexity 2009 - Wadern, GermanyDuration: Oct 11 2009 → Oct 16 2009

## All Science Journal Classification (ASJC) codes

• Software
• Hardware and Architecture
• Control and Systems Engineering

## Fingerprint

Dive into the research topics of 'Deterministic Approximation Algorithms for the Nearest Codeword Problem'. Together they form a unique fingerprint.