Deterministic Approximation Algorithms for the Nearest Codeword Problem

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point

$v \in \mathbb{F}_2^n$

and a linear space

$L\subseteq \mathbb{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

/log

n

)-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

 = loglog

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\subseteq \mathbb{F}_2^n$

of dimension

k

RPP asks to find a point

$v\in \mathbb{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.