Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard
For researchers in computational complexity and tensor methods, this establishes that tensor spectral norm computation is fundamentally limited by real algebraic feasibility, not just non-convex optimization.
The paper proves that the decision problem for the spectral norm of a tensor (tensor spectral threshold) is ∃ℝ-hard, meaning it is at least as hard as deciding the feasibility of a system of polynomial equations over the reals. The reduction is from bounded quartic equality feasibility.
We study the decision version of tensor spectral norm from the viewpoint of real algebraic complexity. For a rationally specified tensor, the tensor spectral threshold problem asks whether its spectral norm exceeds a prescribed rational threshold. Since the feasible domain is compact, attainment itself is trivial; the meaningful question is the threshold decision problem. We prove that this problem is $\exists\mathbb{R}$-hard by giving an explicit polynomial-time reduction from bounded quartic equality feasibility. The reduction first transforms bounded quartic feasibility into homogeneous quadratic sphere feasibility by homogenization, box encoding, and quadratic lifting. It then maps the resulting homogeneous quadratic system to a quartic form whose maximum over the unit sphere separates feasible from infeasible instances. Finally, the quartic form is represented as a symmetric order-four tensor, yielding the desired tensor spectral threshold instance. The result shows that the computational obstruction in tensor spectral norm is not merely non-convex optimization or combinatorial hardness, but real algebraic feasibility itself.