CS Paper Radar

The planted tensor problem over finite fields: algorithms and cryptography

Yuxuan Liu, Youming Qiao, Gang Tang, Chuanqi Zhang

cs.DS cs.CR ·submitted 2026-09-25 13:32 UTC · v1

Abstract

Inspired by the planted clique problem for random graphs, we introduce the planted totally-isotropic space problem for random tensors as follows. Let $U\cong \mathbb{F}_q^n$ and $W\cong \mathbb{F}_q^m$ be finite-dimensional vector spaces over a finite field $\mathbb{F}_q$. Given $d\in \mathbb{N}$, choose a random \(d\)-dimensional subspace \(V\leq U\), and construct a random alternating bilinear map $φ:U\times U\to W$ subject to the constraint \(φ(V,V)=0\). Such a $V$ is known as a totally-isotropic space of $φ$, and the goal is to recover $V$. Building on the recent probabilistic analysis of random tensors (Pham--Qiao--Wigderson--Wigderson, \emph{in progress}), we initiate the study of the algorithmic hardness of this problem. Setting $m=\lceil n/\log n\rceil$, we show that this problem admits an average-case polynomial-time algorithm for $d\geq n/2$, by leveraging recent advances on the non-commutative rank problem. We also show that this problem admits a $q^{O(n\log n)}$-time algorithm. We carry out algorithmic experiments using polynomial-system solving. From these results, we conjecture that the planted totally-isotropic space problem for $d=\lceil n/C\rceil$ with some constant $C\geq 3$ is exponentially hard. Based on this evidence of computational hardness, we explore cryptographic applications of the planted totally-isotropic space problem and related planted tensor problems. We present private simultaneous messages and secret sharing protocols based on planted tensor problems, following the protocols based on planted subgraphs in (Abram--Beimel--Ishai--Kushilevitz--Narayanan, \emph{TCC}'23). At the same security level, the public information size of protocols based on planted subgraphs is (moderately) exponential in that of protocols based on planted tensors, while the communication costs of these protocols are polynomially related.

Comment
40 pages

Closest papers

Nearest neighbours by meaning across the whole index.

MDS codes containing a fixed subcode over finite field extensions

cs.IT math.NT ·2026-10-25 ·Yangcheng Li, Pingzhi Yuan
theoryhot direction similarity 0.64
Abstract · 17 Pages

Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from \(U\). Its full-weight words characterize the desired MDS completions. We prove that \(U\) admits an \([n,k]\) MDS completion over some finite extension of \(\mathbb{F}_q\) if and only if \(d(U)\ge n-k+1\). When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is \[\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{χ_{δ_GM(G)}(q^m)}{q^m-1},\] where $G$ is a generator matrix of $U$, $δ_GM(G)$ is its represented derived matroid, and $χ_{δ_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.

0.28

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.63
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

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.59
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.58
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

Hardness of Unique Shortest Vectors and Bounded Distance Decoding

cs.CC ·2026-11-06 ·Sergei Kudria, Jason Luo
theory similarity 0.58
Abstract · v2

We prove randomized NP-hardness of the unique shortest vector problem (uSVP) at every constant uniqueness factor greater than one, and of bounded distance decoding (BDD) at every fixed positive fraction less than one half of the minimum distance, in both their threshold decision and search versions. Both results hold in every fixed $\ell_p$ norm with $1\le p<\infty$. Previous Euclidean NP-hardness results for the search versions reached uniqueness factors tending to one and decoding radii greater than the minimum distance divided by $\sqrt2$. For linear codes over every fixed finite field and each fixed ${0<ρ\le1/2}$, the decision version of BDD with radius strictly less than $ρ$ times the minimum distance is equivalent under deterministic polynomial-time reductions to satisfiability for circuits promised to have at most one satisfying input. It is therefore NP-hard under randomized polynomial-time reductions. Earlier hardness for decoding general codes applied beyond half the minimum distance. For every fixed $p>2$ and for $p=\infty$, there is a constant $ε>0$ such that, under randomized polynomial-time reductions, uSVP in the $\ell_p$ norm is NP-hard at uniqueness factor $n^ε$, and BDD in the $\ell_p$ norm is NP-hard at radius $λ_1/n^ε$, where $n$ is the lattice rank and $λ_1$ is its minimum distance.

0.18

Product Expansion of Random Codes via Analytic Techniques

cs.IT cs.CCcs.DM ·2026-10-01 ·Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner
similarity 0.57
Abstract · 100 pages. New results in Part II and fixed typos

Beginning with the work of Dinur, Lin, and Vidick (FOCS, 2024), tensor codes with constant product expansion have been foundational to recent advances in quantum locally testable codes (qLTCs) based on cubical complexes. Informally, product expansion says that any low-weight parity check of the tensor code can be written as the sum of few parity checks of each component code in each dimension. Recent work of Kalachev and Panteleev (FOCS, 2025) showed that tensors of random linear codes have constant product expansion. In this work we initiate the study of random linear codes with prescribed automorphism groups. For every sufficiently large prime $k$, we construct pairs of rate $1/2$ MDS codes of length $2k$, over finite fields whose size depends on $k$, that have constant two-sided product expansion and are invariant under the simultaneous cyclic shift of two cycles of length $k$. This shift is the local action in the cube complexes of Rungtanapirom, Stix, and Vdovina (Internat. J. Algebra Comput., 2019). Along the way we give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of [KP25], does not rely on explicit constructions of asymptotically optimal locally testable codes. Our proof relies on several new techniques that we view as interesting in their own right. Instead of working directly over finite fields, we work over the reals and use random Rademacher matrices for the generator matrices of the component codes. From here, we show how to relate product expansion to the operator norm of sparse restrictions of carefully chosen Gram matrices, which we bound using tools from random matrix theory. More generally, we propose a method for studying properties of random linear codes by lifting to random codes over $\mathbb{R}$ and $\mathbb{C}$, which we anticipate will be applicable more broadly to existential problems in coding theory.

0.13

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

cs.IT math.CO ·2026-11-05 ·Alessandro Giannoni
similarity 0.56
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

On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate

cs.CC ·2026-10-29 ·Venkata Gandikota, Vatsal Jha, S. Venkitesh
similarity 0.56
Abstract · A longer version of this manuscript has been submitted for publication

In this work, we investigate the hardness of computing minimum distance, as well as the hardness of syndrome decoding, for rank-metric codes. It is known (Gaborit and Zémor, IEEE TIT 2016) that for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$, minimum distance when $m=O(N)$ and syndrome decoding when $m=O(N^2)$ are NP-hard under randomized reductions. We obtain a derandomization of these results and a bit more. We show that for any fixed small $\varepsilon>0$, for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$ with $m=O(N^{1+\varepsilon})$, the problems of minimum distance, nearest codeword, and syndrome decoding are NP-hard under deterministic reductions. Further, we can prescribe the rate; that is, if we restrict to codes having any fixed rational rate $R\in(0,1)$, then the NP-hardness for all three problems persists. Our main technical contribution is simple, and possibly of independent interest. The reduction of Gaborit and Zémor (IEEE TIT 2016) relies on a distance-preserving embedding of a Hamming-metric code into a rank-metric code, obtained by multiplying its coordinates by a uniformly random vector. We show that we can choose an explicit vector from a slightly larger extension field.

0.18