Improved ways to find distant vectors from linear subspaces
Improved Algorithms for the Remote Point Problem
Computational ComplexityData Structures and Algorithms
Summary
The Remote Point Problem asks how to find a vector that is very different from all vectors in a given linear space. The authors show that over rational numbers, the problem can be solved optimally using a fast algorithm. For vectors over finite fields, they improve previous methods to find vectors that are far away in terms of differing entries. This helps in understanding how to construct hard-to-approximate objects related to computer circuits.
What this means in practice
- •For algorithm designers: Use improved algorithms to find vectors far from a subspace, aiding constructions in coding and complexity theory.
- •For cryptography engineers: Incorporate better distance-finding algorithms over finite fields to enhance hardness assumptions in cryptographic schemes.
A theory result. No direct application yet.
Authors
Ben Lee Volk
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 $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.