CS Paper Radar

Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard: A Reduction from the Ising Model on Planar Cubic Graphs

Michael Emmerich

cs.CG cs.CCphysics.comp-ph ·submitted 2026-08-24 17:09 UTC · v3
theory

Abstract

We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^\circ$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly.

Comment
Keywords: Riesz energy, subset selection, NP-completeness, geometric optimization, planar cubic graphs, independent set, Ising model, computational geometry Update V3.0: Adversarial proof audit with Claude Fable 5 and augmented Git with lean proof support and audit result. Sharpened some constants. No fundamental changes or new results w.r.t. previous versions

Closest papers

Nearest neighbours by meaning across the whole index.

Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection

cs.CG cs.CCcs.DS ·2026-11-10 ·Michael Emmerich, Soumen Atta
code/data similarity 0.60
Abstract · 35 pages, 6 figures. Code, data, and instructions for reproducing the experiments: https://github.com/emmerichmtm/PCGA-Riesz

We choose $k$ of $n$ sites to minimize Riesz $s$-energy, in which a pair at distance $t$ contributes $t^{-s}$. For $s=2$, exact selection is polynomial on a line but NP-hard in the plane. Adapting the proxy lemma of Ceccarello et al. gives an efficient parameterized approximation scheme (EPAS) for fixed Euclidean dimension and fixed $s>0$. To sharpen the bound, we start with a geometric packing. Farthest-first traversal gives $2k$ centers separated by at least the last insertion distance $r$. If one site of an optimum is removed, each of the $k-1$ remaining sites excludes at most one center closer than $r/2$, leaving at least $k+1$ centers free. The new step is a discrete exchange bound: the removed site's interaction energy is at most the average it would contribute at those free centers. In the plane at $s=2$, this reduces the representative bound from $O(k^2\log(2k)/\varepsilon^2)$ for a packing estimate of total energy to $O(k\log(2k)/\varepsilon^2)$, independently of $n$. Rational planar examples show that the resulting separation scale $r/\sqrt{\log(2k)}$ is sharp. A $(1+\varepsilon)$ approximation on rational planar sites takes $O(nk+n\log n)+(C\log(2k)/\varepsilon^2)^k$ operations of polynomial bit cost. The observed number $M$ of representatives determines the search size $\binom{M}{k}$. With one million sites, $k=5$ and $\varepsilon=1/2$, the exchange grid left 252 subsets on clustered inputs and about $9.3\times10^{26}$ on uniform inputs. The method extends to metrics of bounded doubling dimension and to compact domains with effective geometric routines, including filled simple polygons. At $s=2$, exact decision on metrics with nonzero distances in $\{1,2\}$ is W[1]-complete in $k$. A gap that shrinks with $k$ rules out a deterministic EPAS on unrestricted metrics unless FPT = W[1].

0.49

Deterministic Approximation of the Total Variation Distance Between Spin Systems

cs.DS ·2026-10-08 ·Zelin Li, Minji Yang
similarity 0.55
Abstract

We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.

0.23

The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth

cs.DS cs.DM ·2026-10-30 ·Ijay Narang
similarity 0.54
Abstract

We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth. Given any $n$-vertex graph $G$, let $k_η= k_η(G)$ count normalized-Laplacian eigenvalues strictly below $η$. For $\varepsilon > 0$, an $\varepsilon$-approximate counting algorithm outputs an estimate $\widehat Z$ of the partition function $Z$ satisfying $(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z$ with probability at least $3/4$. An $\varepsilon$-approximate sampling algorithm outputs a configuration whose distribution is within total variation distance $\varepsilon$ of the target distribution. We give the following results: (a) Ferromagnetic Potts. Fix $q\ge2$ and $η\in(0,1]$. There exists $β_0(q,η)$ such that, for every inverse temperature $β\geβ_0$, the zero-field $q$-state Potts model admits approximate counting and sampling algorithms: (i) On arbitrary graphs in time $\exp(O(k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) Fix $Δ\ge 3$. On $Δ$-regular graphs of girth $g$ in time $\exp(O(n e^{-g})) \operatorname{poly}(n,1/\varepsilon).$ (b) Bipartite hard-core. Fix $Δ\ge3$ and $η\in(0,1]$. There exists $λ_0(Δ,η)$ such that, for every fugacity $λ\geλ_0$, the hard-core model admits approximate counting and sampling: (i) On $Δ$-regular vertex-transitive bipartite graphs in time $\exp(O (k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) On $Δ$-regular bipartite graphs of girth $g$ in $\exp(O(n e^{- g}))\operatorname{poly}(n,1/\varepsilon).$ All four results follow from verifying the hypotheses of a new framework we call C-3PO. At a high level, the C-3PO algorithm proceeds by enumerating small cuts and reconstructing the original measure through cluster expansions. Underlying the algorithm is an improvement of subspace enumeration methods via active regression.

0.29

Universal optimality on finite Lee tori

cs.IT math.CO ·2026-11-12 ·Tao Zhang
theory similarity 0.54
Abstract · 30 pages

We study subsets of finite Lee tori that minimize pair energy among sets of the same cardinality for every discretely completely monotone potential. At half occupancy on a product of even cycles, the two checkerboards minimize both total pair energy and maximum individual energy. They are the only minimizers for every nonconstant classical completely monotone potential on $(0,\infty)$, proving the checkerboard conjecture of Bouman, Draisma, and van Leeuwaarden for this class. At the independence number of the distance one graph on $\Z_q^n$, universally optimal sets exist exactly when $q$ is even, $q=3$, $n=1$, or $(q,n)=(5,2)$. In these cases they are precisely the maximum independent sets and form a single Lee isometry class. At density $1/5$ in $\Z_5^n$, $n\ge2$, universal optimality is characterized by a weighted count of pairs at distances one and two. We prove these results using integer box occupancy bounds that strengthen Fourier linear programming and, in the quinary case, Fourier certificates with a common zero set.

0.37

The Honeycomb Framework for Code Bounds

cs.IT cs.DM ·2026-08-20 ·William Gay, Fernando Granha Jeronimo, Lenny Liu
theoryhighly cited similarity 0.53
Abstract

We introduce the honeycomb hierarchy, a representation-theoretic framework that gives new asymptotic upper bounds on $R_2(δ)$. Its first level is the two-row hyperoctahedral representation graph associated with type $S^{(n-k,k)}$. Retaining every two-row irreducible and every coordinate box-transfer channel, together with a moving-projection theorem, yields an explicit four-parameter exponent $κ_{\mathrm{HC}}$. The earlier whole-cube exponent $κ_H$ is a boundary restriction of this optimization, whereas the fully optimized second MRRW exponent $M_2$ is an exact symmetric slice. The prior best curve is the combined $κ_{\mathrm{bin}}=\min\{κ_{\mathrm{CW}},κ_H\}$, which uses a constant-weight branch $κ_{\mathrm{CW}}$. Replacing only the whole-cube branch by the honeycomb bound gives $κ_{\mathrm{best}}=\min\{κ_{\mathrm{CW}}, κ_{\mathrm{HC}}\}$. We prove, on $0<δ<1/2$, \[ R_2(δ)\le κ_{\mathrm{best}}(δ) \le κ_{\mathrm{bin}}(δ) \le R_{\mathrm{2MQC}}(δ)<M_2(δ),\\[-1mm] κ_{\mathrm{best}}(δ) \le \min\{κ_{\mathrm{CW}}(δ), κ_{\mathrm{bal}}(δ)\} <R_{\mathrm{2MQC}}(δ), \qquad κ_H(δ)=R_{\mathrm{MQC}}(δ). \] The hierarchy has two further directions. Increasing the representation depth replaces scalar by matrix-valued transfers on the hive. Increasing the anchor depth localizes it in a stable-set hierarchy. The resulting bounds are monotone in both directions and eventually recover $A_2(n,d)$. A complementary Horn--channel hierarchy gives matrix optimizations whose $2\times2$ level is $κ_{\mathrm{HC}}$ and whose $3\times3$ level is a stronger bound. Already at low levels, they can be used to improve the strongest previous general bounds, while the honeycomb framework provides a route towards tighter bounds.

0.46

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.53
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

On the Complexity of Computing with p-adic Lattices

cs.SC math.NT ·2026-10-28 ·Pierre Fromonot, Mercedes Haiech, Tristan Vaccon
theory similarity 0.52
Abstract

We study the complexity of two fundamental problems attached to p-adic lattices: computing an N-orthogonal basis, and deciding whether a given basis is N-orthogonal. When the norm is supplied through an explicit diagonal representation, both problems are polynomial. However, in the black-box model, where the ultrametric norm N is fixed and only accessible through an evaluation oracle, we prove that both problems require $Ω$(p^{v-1} ) queries in the worst case, where v $\le$ n is the largest multiplicity of a commensurability class of N and n is the dimension of the ambient vector space. We then analyse the optimality of these bounds by providing explicit algorithms. Our results answer formally an open question of Zhang, Deng and Wang and refine the recent results of Duan and Wu by providing pointwise query bounds depending on the norm's structure, in addition to uniform bounds.

0.14

Binary Belief Propagation Fixed Points: Finiteness, Rigidity, and Topological Complexity

cs.IT math.AGmath.CO ·2026-11-09 ·Yusuke Watanabe
theorycode/data similarity 0.52
Abstract · 37 pages, 3 figures. Lean 4 formalization and interval certificates at https://github.com/ywatanabex/bp-response-geometry-lean

A fixed finite binary Ising model has only finitely many admissible complex belief propagation fixed points, even at degenerate parameter values. Families of positive fixed points obtained by varying external fields can nevertheless have nontrivial topology. We study this distinction through the external-field projection. For a fixed field, we prove finiteness by bounding the pole orders of the magnetizations on a hypothetical complex solution curve. The generic degree on the support graph then bounds the total local multiplicity. A graph has a single smooth real line as its full positive response for every choice of positive couplings, base field, and strictly positive sweep direction exactly when it contains no two vertex-disjoint connected subgraphs of cycle rank at least two. Two such subgraphs suffice to create a circular component. For a plane obtained by varying two vertex fields, connected simple bipartite cubic graphs with one uniform coupling and a universal bound on the fixed fields realize every genus. The minimum number of vertices grows logarithmically in the genus, by a matching algebraic upper bound on Betti numbers. Finally, we certify the complete field discriminant of an eighteen-vertex product model and recover its torus component's genus from the counts of distinct roots on all field cells. The three main theorems, including the logarithmic size bounds, are formally verified in Lean 4 with Mathlib.

0.31