Improved Algorithms for the Remote Point Problem

Ben Lee Volk

In the authors' words

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq F^{n}$ of dimension $k$ , to deterministically find a vector $v \in 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 $Ω (\frac{n}{m a x { k , l o g n }} lo g n)$ .

Main resultLimitation the authors admit

Improved Algorithms for the Remote Point Problem

In the authors' words

More on Algorithms & complexity that day

4-Block Integer Programming is in FPT

Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

Analysis of trade-offs in urban heat mitigation using a Bayesian Optimization framework for an urban canopy layer model

Factorisability of Low Dimensional Non-Negative Integer Matrices