Improved Algorithms for the Remote Point Problem

Abstract

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L\subseteq {\mathbb{F}}^n$ of dimension $k$, to deterministically find a vector $v\in {\mathbb{F}}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $\Omega \left(\frac{n}{\max \{k,\log n\}}\log n\right)$.