CS Paper Radar

Explicit Subspace Evasive Sets via Subspace Designs

Joshua Brakensiek, Yeyuan Chen, Mahdi Cheraghchi, Rohan Goyal, Venkatesan Guruswami, Aaron Putterman, Zihan Zhang

cs.DM cs.ITmath.CO ·submitted 2026-11-11 02:04 UTC · v1

Abstract

Given a finite field $\mathbb F_q$, we say that a set $A\subseteq \mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\subseteq \mathbb F^n_q$ with bounded dimension $\dim(U)\leq r$, the intersection size $|A\cap U|$ is at most $c$. The probabilistic method shows the existence of $(r,c)$ subspace evasive sets with $|A| = q^{(1-ε) n}$ with $c = O(r/ε)$. However, the best explicit constructions by Dvir--Lovett (STOC 2012) and Ben-Aroya--Shinkar (CJTCS 2013) have $c$ growing as an exponential function of $r$. Here, we give an explicit construction of such subspace evasive set that achieves the intersection bound $c=O(\min(r\log(r/ε)/ε, r^2/ε))$ when both $r$ and $1/ε$ are constants. Our approach is simple and the key idea is to compose subspace design codes (Guruswami-Xing, STOC 2013) with a suitably chosen ``local'' subspace evasive set. As a corollary, we give the first construction of an explicit (strongly) capacity-achieving list-recoverable code with nearly optimal list size, circumventing all previously-known barriers to construction.

Comment
27 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Evasive subspaces, minimal rank-metric codes and subspace designs via auxiliary fields

cs.IT math.CO ·2026-11-05 ·Alessandro Giannoni
similarity 0.67
Abstract · 33 pages

We extend the auxiliary-field method for scattered subspaces to evasive subspaces and subspace designs. For $1\le h\le k<hn$ and coprime $h,k+1$ with $n(k-h+1)\ge k+1$, we construct spanning $(h,k)$-evasive $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^n}^r$ of dimension $rn(k-h+1)/(k+1)$ in every sufficiently large admissible ambient dimension, with a threshold independent of $q$. When $k<n$, this dimension is maximum. The proof combines an intersection lemma, a rank-support density inequality, scalar orbit counting, and a profile preserved by direct sums. The coding consequences include, for every fixed odd extension degree $m\ge3$ and every sufficiently large $K$, minimal rank-metric codes of optimal length $2K$ with first two generalized weights $(m+1)/2$ and $m+1$. For these codes the stable profile is equivalent to minimality with the largest possible minimum distance; for even $m$ the analogous class consists of minimal MRD codes. More generally, for $1\leτ\le m-2$ and $\gcd(m,τ+1)=1$, we obtain nondegenerate $τ$-minimal codes of length $(τ+1)K$ for every sufficiently large $K$, uniformly in $q$. We also construct maximum $h$-designs whose number of members grows exponentially with the ambient dimension at fixed $q,n,h$, and the associated maximum sum-rank distance (MSRD) codes with a growing number of equal long blocks. In extension degree five, the ordinary and $2$-minimal constructions hold for every $q$ and every $K\ge32$ and $K\ge59$, respectively.

0.09

Algebraic-Geometric Parvaresh--Vardy Subspace Designs and Rank Condensers

cs.CC cs.IT ·2026-09-26 ·Gil Cohen, Dean Doron, Noam Goldgraber
published similarity 0.65
Abstract

A subspace design is a collection of subspaces $H_1,\ldots,H_n$ of $\mathbb{F}_q^k$ with the property that no low-dimensional subspace $W$ intersects the collection "too much". Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension $t$ of each $H_i$ is equal to the dimension of $W$, for every constant field size our construction attains $n=Ω(k)$ and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with $t$ (or $k$). Our subspace designs also imply new constructions of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on $k$ while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank $r$, for all $r < q$, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh--Vardy codes (Parvaresh--Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis -- tailored to affine sources -- of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC '12) we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.

0.59

Construction of Regular Fat Linear Sets and Non-Representable q-Matroids

cs.IT math.CO ·2026-10-12 ·Yufei Qiu, Valentino Smaldore, Zhenpeng Wang, Corrado Zanella, Ferdinando Zullo
similarity 0.60
Abstract

Let $q$ be a prime power. An $(r, i)$-regular fat $\mathbb F_q$-linear set has exactly $r$ points of weight $i\ge2$, called fat points. All of its remaining points have weight one, and at least one such point occurs. We solve two open problems posed by three of the authors of this paper. First, we derive divisibility constraints on the point weights using the scalar stabilizer of the defining subspace. Consequently, a regular fat linear set of rank $2i$ in $\operatorname {PG}(1,q^n)$ has at most two or exactly $q + 1$ fat points. In the latter case, the fat points form an $\mathbb F_q$-subline. Second, we construct higher-dimensional regular fat linear sets whose fat points do not form an $\mathbb F_q$-subgeometry. In particular, for every $k\geq 3$ we obtain examples of rank $2k$ whose fat locus consists of an $\mathbb F_q$-subgeometry $\operatorname {PG}(k-2,q)$ in $\operatorname {PG}(k-1,q^4)$ together with one external point. This construction is then generalized further. Finally, we apply our projective-line results to $q$-matroid representability and present an infinite family of non-representable rank-two $q$-matroids arising from partial spreads.

0.25

A probabilistic construction of maximum $h$-scattered subspaces

cs.IT math.CO ·2026-10-23 ·Alessandro Giannoni, Alessandro Neri
theory similarity 0.59
Abstract

Let $1\le h\le n-2$ and $g=\gcd(n,h+1)$. We prove that, for every prime power $q$, a maximum $h$-scattered $\mathbb{F}_q$-subspace of $V(r,q^n)$ exists whenever $(h+1)\mid rn$ and $$r\ge\frac{h+1}{g}\bigl(h(n-h-2)+1\bigr).$$ In particular, for fixed $n$ and minimum distance $δ\in\{2,\ldots,n-1\}$, $\mathbb{F}_{q^n}$-linear MRD codes of length $N$ exist for every $q$ and every sufficiently large $N$ such that $n$ divides $(n-δ+1)N$, with a bound on $N$ depending only on $n$ and $δ$. We take the $\mathbb{F}_{q^s}$-span of the columns of a random matrix $A$ over the algebra $R=\mathbb{F}_{q^n}\otimes_{\mathbb{F}_q}\mathbb{F}_{q^s}$, for a suitable $s$. Such a subspace is maximum $h$-scattered if and only if the kernel of $A$ contains no nonzero vector whose expansion with respect to an $\mathbb{F}_q$-basis of $\mathbb{F}_{q^s}$ has rank weight at most $h+1$. When $\gcd(n,s)=1$, $R$ is a field, and a first-moment argument, counting these vectors up to multiplication by $\mathbb{F}_{q^n}^*\mathbb{F}_{q^s}^*$, shows that with positive probability the kernel contains none of them if $s>h(n-h-2)$. When $d=\gcd(n,s)>1$, $R$ is a product of $d$ fields, and vectors vanishing in some factors lie in the kernel with larger probability. We control them by proving that, for an $(h+1)$-dimensional $\mathbb{F}_q$-subspace $D$ of $\mathbb{F}_{q^n}$, the elements of $D\otimes_{\mathbb{F}_q}\mathbb{F}_{q^s}$ vanishing outside $k$ given factors, $0<k<d$, form an $\mathbb{F}_{q^s}$-space of dimension at most $(h+1)k/d$, with equality only if $D$ is linear over a subfield of $\mathbb{F}_{q^n}$ larger than $\mathbb{F}_q$. Taking $s=gr/(h+1)$ gives the bound on $r$. Finally, if $(n-h-1)\mid(h+1)$, then for every $r$ satisfying the above inequality there is an $h$-scattered $\mathbb{F}_q$-subspace of $V(r,q^n)$ of dimension $\lfloor rn/(h+1)\rfloor$, without a divisibility condition on $rn$.

0.50

Covering radius of rank-metric codes via covering lifts and clubs

cs.IT math.CO ·2026-10-08 ·Giuseppe Marino, Alessandro Neri, Alessia Vallefuoco
theory similarity 0.58
Abstract

We introduce a generator-matrix-based geometric approach to the covering radius of $\mathbb F_{q^m}$-linear rank-metric codes. Starting from the $q$-system associated with the code, we define the notion of covering lift and show that the covering radius can be recovered from the hyperplane weights of such lifts. This yields an exact criterion, in terms of the length and effective length of the code, for the covering radius to attain its largest possible value, together with the upper bound $ρ(\mathcal{C})\le \min\{m,n\}-1$ in all remaining cases. We then specialize our approach to $1$-dimensional codes, for which the effective length coincides with the minimum rank distance. In this setting, codes attaining $ρ(\mathcal{C})= \min\{m,n\}-1$ are related to covering lifts that are clubs. More generally, we characterize this case through linear maps into suitable quotient spaces, obtaining equivalent interpretations in terms of generalised evasive subspaces and auxiliary matrix rank-metric codes. These results determine the covering radius for several boundary values of the minimum distance and for all $1$-dimensional codes with extension degree $m\in\{3,4,5\}$. For $m=6$ and every $q$ we provide constructions and, for $q\in\{2,3\}$, computational results showing that $1$-dimensional rank-metric codes with the same length and minimum distance can have different covering radii.

0.05

Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

cs.CC quant-phmath.AGmath.NT ·2026-08-25 ·Yota Maeda, Hiroshi Yano
theory similarity 0.57
Abstract · 31 pages

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.

0.28

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.57
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)$.

0.35

CSS Quantum LRCs with Intersecting Recovery Sets: Constructions and Bounds

cs.IT quant-ph ·2026-08-11 ·Evagoras Stylianou, Vinayak Ramkumar, Holger Boche, Rawad Bitar
similarity 0.56
Abstract · Accepted for presentation at the 2026 IEEE Information Theory Workshop (ITW 2026)

In this work, we study $(r,t,x)$ quantum locally recoverable codes (qLRCs) with locality $r$, $t$ recovery sets per qudit, and intersection parameter $x$. We first show that, assuming the underlying classical codes have dual minimum distance at least two, a CSS code is an $(r,t,x)$-qLRC if and only if the underlying classical codes are $(r,t,x)$ classical LRCs (cLRCs) with common recovery sets. We then use subset-inclusion matrices to construct families of binary dual-containing $(r,t,x)$-cLRCs, which yield binary $(r,t,x)$-qLRCs via the CSS construction. For CSS $(r,t,x)$-qLRCs, we derive upper bounds on the dimension and rate, minimum-distance bounds in the pure case, and a Singleton-like dimension bound in the exact case. Finally, we show that these families attain high rates and nontrivial minimum distances.

0.49