CS Paper Radar

On integral polytopes related to Edmonds' problem

Hiroshi Hirai

cs.DM math.CO ·submitted 2026-09-17 04:57 UTC · v1

Abstract

In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix $A = \sum_{k=1}^m A_k x_k$. We regard them as linear optimization over integral polytopes ${\cal P}(A)$ and ${\cal Q}(A)$, respectively, which are obtained by the convex hulls of exponent vectors of subdeterminants of~$A$ and its blow-ups $A^{\{d\}} = \sum_{k=1}^m A_k \otimes X_k$ $(d=1,2,\ldots)$. By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes ${\cal P}(A) \subseteq {\cal P}^{\leq 2}(A) \subseteq {\cal P}^{\leq 3}(A) \subseteq \cdots = {\cal Q}(A)$ and show that the integrality gap of ${\cal Q}(A)$ relative to ${\cal P}(A)$ is at least $1/2$. Further, we show that if each $A_k$ is rank-2 skew-symmetric, then the above hierarchy terminates at the second level and the integrality gap is improved to $2/3$.

Closest papers

Nearest neighbours by meaning across the whole index.

A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results

cs.LG math.COmath.FA ·2026-08-16 ·Zijian Zeng, Houde Liu, Kurunathan Ratnavelu
theory similarity 0.62
Abstract · 9 pages, 0 figure,

For $m\geq 2$, let $c_p(m)$ be the all-dimensional best constant in $$ \left\|\sum_{k=1}^m A_k\right\|_p \leq c_p(m)\left\|\sum_{k=1}^m |A_k|\right\|_p. $$ Tang and Zhang conjectured an explicit formula for every finite $p>1$. We disprove the conjecture with two explicit real $2\times 2$ rank-one matrices at $p=3/2$. The comparison is certified by seven strict rational inequalities and, in particular, places the attained ratio above $207/200$, while the conjectured constant lies below $207/200$. On the positive side, we prove the conjectured sharp bound for every family of rank-at-most-one summands when $2\leq p<\infty$, and classify all equality cases. We also prove the corresponding endpoint statement for $p=\infty$. Finally, for arbitrary complex matrices, we establish the conjectured sharp constant in the case $m=2$, $p=4$.

0.44

Nonnegative Rank Bounds for the Algebraic Monotone Calculus

cs.CC ·2026-10-31 ·Fedor Part
theory similarity 0.60
Abstract

In Hrubes' Algebraic Monotone Calculus a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $χ(A)-εχ(1)$ for some $ε>0$, where the coefficient of $χ(A)$ at $x^σ$ counts the terms of $A$ satisfied by $σ$, and $χ(1)=\prod_i(x_i^0+x_i^1)$. Proof size is circuit size, and $ε$ is existentially quantified, so lower bounds must hold at arbitrarily small $ε$. We prove lower bounds for bounded-depth fragments by two nonnegative rank measures of the target: monotone tensor rank and the nonnegative rank of a flattening. At depth three a proof is a nonnegative tensor decomposition. Restricting its terms to subcube indicators gives conical juntas, a system polynomially equivalent to Sherali-Adams in twin variables. For arbitrary terms we adapt Rothvoss' hyperplane separation to monotone tensor rank: Tseitin formulas on constant-degree expanders of large girth need proofs of size $2^{Ω(εn)}$ whenever $ε=ω(\log n/n)$. This cannot reach every $ε$: at shift $2^{-Θ(n\log n)}$ Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every $ε\geq2^{-Ω(n)}$, converting a Sherali-Adams degree bound into a size bound. Depth three is essential: Tseitin has monotone proofs of size $O(n^3)$ and depth $O(\log n)$ at every $ε$. Beyond depth three we bound the nonnegative rank of a flattening by $L^{2^t}$ for a monotone formula with $L$ leaves and mixed-product depth $t$: the largest number of product gates on a root-to-leaf path whose two inputs each meet both sides of the bipartition. Approximate extension complexity then bounds perfect matching and odd factor instances, and planted CSP integrality gaps give an explicit family of planted Tseitin DNFs hard at inverse-polynomial shift.

0.25

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.60
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

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.58
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

Equitable Subpartitionability Does Not Characterize Box-TDI Polyhedra

cs.DM ·2026-10-09 ·Emiliano Lancini, Francesco Pisanu
similarity 0.57
Abstract · 6 pages

Equitable subpartitionability (ESP) is a sufficient condition for an integral system to be box-totally dual integral. We show that the converse fails even when alternative descriptions of the same polyhedron are allowed. We provide a geometrical characterization of polyhedra that can be described by ESP systems in terms of normal cones. We construct a four-dimensional integer polytope described by a totally equimodular matrix that admits no integral ESP description. This answers negatively a previously posed question by the same authors.

0.18

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

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.57
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

Weighted Matroid Intersection under Minimum Rank Oracle

cs.DM math.COmath.OC ·2026-11-07 ·Taihei Oki
theory similarity 0.56
Abstract

We consider matroid intersection under the minimum rank oracle model, in which two matroids are accessible only through an oracle that returns the minimum of the ranks of a given set in the two matroids. By Edmonds' theorem, this oracle determines the matroid intersection polytope, although it does not reveal the exchangeability graphs on which classical algorithms rely. Recent work by Bárász, Bérczi, Király, Oki, Yamaguchi, and Yokoi (2025) showed that unweighted matroid intersection is polynomially solvable in this model. In this paper, we present a strongly polynomial-time algorithm for weighted matroid intersection in this model. The key to our algorithm is a polynomial-size extended formulation of tangent cones of common base polytopes that can be constructed using the minimum rank oracle. We also give min-max theorems in terms of the minimum rank function via 1/3-submodularity, and present a strongly polynomial-time algorithm to compute an optimal dual solution.

0.14

Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions

cs.SC math.OC ·2026-11-04 ·Didier Henrion, Alaa Ibrahim, Victor Magron
similarity 0.56
Abstract

We consider linear conic problems whose cone is a product of truncated quadratic modules, the sum-of-squares (SOS) side of the moment-SOS hierarchy. A floating-point solution is turned into an exact rational certificate in three steps: rounding, repair of each block residual by a constant, and absorption of the constants along a recession direction of the problem. The repair relies on strict partitions of unity in the quadratic modules. We characterize their existence, relate the canonical one to the analytic center of the dual pseudo-moment cone, Christoffel-Darboux polynomials and Pell equations, and we derive closed-form rational partitions for balls and boxes. The loss incurred by the certification is the optimal value of a recession problem, equal to a support function of the masses of the dual feasible pseudomoments. The method is illustrated on polynomial optimization, volume computation and positivity of polynomials along D-finite trajectories.

0.26