2026-07-23T04:16:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2413 2024-03-06T11:09:01Z ddc:004 open_access

Deterministic approximation algorithms for the nearest codeword problem Alon, Noga Panigrahy, Rina Yekhanin, Sergey The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in F_2^n and a linear space L in F_2^n of dimension k NCP asks to find a point l in 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 effcient 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, (almost) de-randomizing the randomized algorithm of Berman and Karpinski. We also initiate a study of the following Remote Point Problem (RPP). Given a linear space L in F_2^n of dimension k RPP asks to find a point v in 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 Omega(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noga Alon and Rina Panigrahy and Sergey Yekhanin 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09421.4 urn:nbn:de:0030-drops-24133 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.4 eng https://creativecommons.org/licenses/by/4.0/legalcode