CS Paper Radar

Levenshtein-type bounds for $(a,b)$-avoiding spherical codes

Peter Boyvalenkov, Danila Cherkashin, Peter Dragnev, Peter Grabner

cs.IT math.COmath.MG ·submitted 2026-11-05 21:04 UTC · v1

Abstract

We develop a Levenshtein-type linear programming framework (for maximal $s$-codes and for minimal energy) for $(a,b)$-avoiding spherical codes, that is, codes whose inner products between distinct points avoid $(a,b)$. We introduce and investigate signed measures that are positive definite up to an appropriate degree and yield stationary auxiliary linear programming polynomials and exact quadrature formulas. We give explicit conditions for positivity of the quadrature weights and sufficient Krein-type conditions for nonnegative Gegenbauer coefficients (positive definiteness of the candidate optimal linear programming polynomials). Under these hypotheses and suitable node-location assumptions, the resulting cardinality bounds are optimal within the corresponding degree restriction and unique under natural nondegeneracy conditions. Under proper conditions on the quadrature nodes, we obtain universal lower energy bounds by utilizing Hermite interpolants as polynomial solutions of the respective linear program. Common test functions characterize optimality in the full polynomial linear programs under mild additional assumptions.

Comment
29 pages

Closest papers

Nearest neighbours by meaning across the whole index.

The Rate of the Delsarte Bound for Binary Codes and Spheres

cs.IT math.COmath.MG ·2026-10-15 ·Andrew Salmon
theory similarity 0.63
Abstract · 32 pages, comments welcome

We give the asymptotic rate of Delsarte's linear programming bound for binary codes and spherical codes. This extends previous work of the author which formulated and proved an analogue of the conjecture of Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini for binary codes, obtaining the rate of the Delsarte linear program at distance $1/2-1/π$. The lower bounds introduce ideas from potential theory into the study of Delsarte's bounds, whereby the measures underlying a system of orthogonal polynomials give an obstacle problem. We solve the resulting obstacle problem in the case of binary codes and spherical codes, obtaining a closed form for the lower bound in terms of elliptic integrals. For the upper bounds, we relate the $N$-qubit construction for binary codes used in previous work of the author to the constructions in OpenAI's Chapter 2 for spherical codes and observe that they both involve interlacing spectra. This leads to a variational problem involving measures constructed from these spectra under the Markov-Krein correspondence. This variational problem admits an exact solution and matches the lower bound.

0.55

Hermite-Fisher bounds and stability for min-entropy power inequalities

cs.IT math.FAmath.MGmath.PR ·2026-09-18 ·Silouanos Brazitikos, Martin Rapaport, Tomasz Tkocz
similarity 0.62
Abstract

We derive explicit lower bounds for relative Fisher information by combining a variational principle with suitably orthogonalized Hermite-polynomial test functions. The resulting cumulant bounds are asymptotically sharp and yield lower bounds for Gaussian entropy deficits. We also establish quantitative versions of sharp min-entropy power inequalities in all dimensions. En route, we develop a stability result for Brzezinski's sharp bound for block sections of products of Euclidean balls, which may be of independent interest.

0.39

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.61
Abstract

Semidefinite programming (SDP), particularly the sum-of-squares (SoS) hierarchy, provides $n^{O(q)}$-time approximation and certification algorithms for optimizing degree-$d$ homogeneous polynomials on the unit sphere. For arbitrary inputs, degree-$q$ SoS gives a powered-objective approximation factor $O_d((n/q)^{d/2-1})$ [BGGLT17]. For random order-$d$ tensors, degree-$d$ SoS has an integrality-gap lower bound of $2^{-O(d)}(n/d)^{d/4-1/2}$ relative to the true spherical maximum; lower bounds also extend to growing SoS degree in tensor PCA [BGL17,HKP17]. We establish lower bounds for weaker linear-programming relaxation hierarchies. Our degree-$q$ moment LPs impose the sphere identities and any prescribed, instance-independent family $\mathcal{G}$ of valid polynomial inequalities of degree at most $q$. They include Sherali--Adams-type product hierarchies. For every even $d\ge2$, constant $C>0$, and $q$ satisfying $2d | q$ and $2d\le q\le n$, every such relaxation with at most $n^{Cq}$ tests has instances $P$ satisfying \[ \frac{\mathrm{PowLP}_{q,\mathcal{G}}(P)}{\|P\|_\infty}\ge \frac{c_{d,C}}{\sqrt{q\log n}}\left(\frac nq\right)^{d/2-1/2}.\] Here $\|P\|_\infty$ is the maximum absolute value of the polynomial over the sphere and $\mathrm{PowLP}_{q,\mathcal{G}}(P)$ is the relaxed objective. The exponent $d/2-1/2$ improves the leading dependence on $d$ relative to the $d/4$-type exponents in prior random-tensor SoS lower bounds. Our LP hierarchies impose weaker positivity conditions than semidefinite moment relaxations. It leaves open whether analogous degree dependence can be achieved in lower bounds for SDP hierarchies.

0.25

Linear Programming Bounds for Locally Recovery Codes II

cs.IT cs.DMmath.CO ·2026-09-12 ·Ming-Hsuan Kang, Maosheng Xiong
similarity 0.60
Abstract · This is a preliminary release. Comments are welcome

We give a polynomial-size linear programming bound for $q$-ary all-symbol locally recoverable codes with locality parameters $(r,δ)$, without assuming linearity. The key idea is to keep, for every ordered pair of codewords and every selected recovery view, the joint Hamming weight on the helper set, the recovered coordinate, and the rest of the code -- rather than collapsing this triple into a single distance, as earlier formulations do. Averaging this three-block distribution over recovery views of the same length yields exact identities linking it to the global distance distribution, together with nonnegative product-Krawtchouk constraints that encode locality and spectral positivity simultaneously. The resulting LP has polynomially many variables, its optimum dominates the ordinary Delsarte bound, and an earlier outside-distance formulation, the convex-hull bound of Li--Wei--Xiong, and the dual-based bound of Gruica--Jany--Ravagnani all arise from it as coarser marginals. Exact rational certificates over $q=2,3,4$ show the bound is strictly stronger than the best of these prior LPs in thirteen of fifteen tested cases, pinning down seven exact maximum code sizes and twelve exact maximum linear dimensions.

0.25

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.56
Abstract

We generalize integer programming to the setting in which the image $A \mathbf{x}$ is restricted to an explicitly given rational polyhedron $P$. That is, we solve $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}\in P, \mathbf{x}\in\mathbb{Z}_{\geq 0}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and $P$ is an explicitly given rational polyhedron. We present a randomized algorithm running in time $(dΔ)^{O(d)}\operatorname{poly}(L)$ in this regime, where $Δ:= \|A\|_\infty$ and $L$ is the binary input length. This running time matches that of the best-known parameterized algorithms for integer programming, due to Eisenbrand and Weismantel and to Jansen and Rohwedder, and improves on the $O(d^2)$ exponent achieved by Dadush, Léonard, Rohwedder, and Verschae in a more general setting. This result enables several applications, including exact algorithms for integer programming and unbounded knapsack in which the consumed resources $A\mathbf{x}$ must satisfy arbitrary additional linear constraints. We also obtain a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant, resolving an open problem of Randolph and Węgrzycki. For integer programs with $m$ constraints and bounded row doubling, we obtain an $f(C,m)n^{O(m)}\operatorname{poly}(L)$-time algorithm and show that the dependence on $m$ in the exponent of $n$ is necessary under $\mathsf{W[1]}\ne\mathsf{FPT}$.

0.24

An Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs

cs.CC ·2026-08-18 ·Pravesh K. Kothari, Andrew D. Lin
published similarity 0.56
Abstract

We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distributions''). As a consequence, we resolve a question left open by the work of O'Donnell and Schramm [OS19] that they had explicitly attributed to the lack of such an inequality. A Cauchy-Schwarz inequality is exactly satisfied by pseudo-distributions satisfying the constraints of the sum-of-squares semidefinite programming hierarchy and already has scores of applications. However, the proof there requires global positive semidefiniteness. Our approximate version, on the other hand, relies only on local positive semidefiniteness satisfied by the Sherali-Adams pseudo-distributions. Our formulation loses an additive error that scales with the L1 norm of the coefficients of the constituent polynomials, and this loss is asymptotically tight. Our proof is elementary and relies on a simple sampling argument. As an application, we resolve a question left open in the work of O'Donnell and Schramm that gives a trade-off between constraint density and the Sherali-Adams degree for refuting random constraint satisfaction problems. Specifically, for odd arity CSPs, we show that the constraint density requirement for a given degree can be improved by a polynomial factor in $n$. Along the way, we observe that by a simple extension, the results in their work extend to a more general semirandom setting.

0.36

The half-rate linear programming bound for binary codes is $\frac12-\frac1π$

cs.IT math.CO ·2026-09-03 ·Andrew Salmon
theory similarity 0.56
Abstract · 33 pages

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/π+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1π\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1π. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

0.52

New Maximum Hermitian $d$-Codes and New Invariants from Skew Polynomial Rings

cs.IT math.COmath.RA ·2026-10-19 ·Paolo Santonastaso, Yue Zhou
theory similarity 0.56
Abstract

Maximum rank-distance codes were introduced independently by Delsarte (1978) and Gabidulin (1985) for unrestricted matrix spaces, and their study was subsequently extended to the classical form spaces of alternating, symmetric, and Hermitian matrices. For Hermitian $d$-codes, Schmidt (2018) established the upper bound and constructed optimal additive codes for all admissible parameters except when $n$ and $d$ are both even and $4\le d\le n-2$. We settle this final open existence case, more generally, construct additive maximum Hermitian rank-metric codes for every admissible length and minimum distance. Rather than working directly in the space of Hermitian matrices, we construct our objects within central simple algebras with unitary involution arising from quotients of skew polynomial rings. We also introduce scalar-field and Lyapunov operators in these algebras, leading to new invariants for the equivalence of additive Hermitian codes. Explicitly determining these invariants yields strong necessary conditions for Hermitian equivalence and demonstrates that our construction contains a large number of pairwise inequivalent codes.

0.45