CS Paper Radar

Two Linear Programs are Better than One

Alexander E. Black, Christoph Hertrich, Stefan Kober, Georg Loho

cs.CC math.COcs.DMcs.LGmath.OC ·submitted 2026-10-11 20:44 UTC · v1

Abstract

The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

Closest papers

Nearest neighbours by meaning across the whole index.

0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems

cs.CC math.OCcs.DM ·2026-10-07 ·Alberto Del Pia
similarity 0.61
Abstract

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP $\cap$ coNP, so it is unlikely to be NP-hard. We answer Chvátal's question negatively already in its most restricted form: for Chvátal rank one, for integer feasibility, and even for the SAT polytopes of formulas whose clauses have at most three literals. Our answer holds under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for integer feasibility on such SAT polytopes of Chvátal rank one would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting the conjectured hardness of approximating lattice problems within polynomial factors. Second, assuming the hardness of learning with errors, an average-case analog of bounded distance decoding, the problem is also hard on average, for a polynomial-time samplable distribution of formulas. This also gives negative answers to related questions of Cornuéjols, Lee, and Li. We first prove these results for parallelepipeds, where they rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our parallelepipeds, such a matrix exists but is hard to find. For SAT polytopes, we represent candidate lattice vectors by their residues modulo small integers, and binary arithmetic on additional 0/1 variables checks that these vectors lie in the lattice.

0.27

On the Representational Geometry of Dynamic Programs

cs.LG cs.DMmath.AGmath.CO ·2026-08-25 ·Richard F. M. Lim, Ruriko Yoshida
theory similarity 0.58
Abstract · 13 pages, 7 figures; submitted to NeurIPS 2026 Workshop on Symmetry and Geometry in Neural Representations (Extended Abstract Track)

Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.

0.26

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

cs.GT cs.CCmath.COmath.OC ·2026-09-21 ·Michel Grabisch and. Hans Raj Tiwary
similarity 0.58
Abstract

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

0.27

Approximate counting of vertices of 0/1 polytopes: a stronger hardness result

cs.CC math.CO ·2026-08-23 ·Heng Guo, Mark Jerrum
similarity 0.57
Abstract

We show that approximately counting the vertices of a bounded 0/1 polytope, presented as a system of rational linear inequalities, is, informally speaking, NP-hard. In particular, there is no FPRAS for this problem unless RP=NP. The proof is by a reduction from approximately counting homomorphisms from a given graph to a particular four-vertex graph. The main proof ideas were found using GPT-5.6 Sol Ultra.

0.45

Weighted Matroid Intersection under Minimum Rank Oracle

cs.DM math.COmath.OC ·2026-11-07 ·Taihei Oki
theory similarity 0.57
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

A Width Hierarchy of Monotone Algebraic Branching Programs

cs.CC ·2026-11-04 ·Julian Dörfler, Alexander Rogovskyy
theory similarity 0.56
Abstract · 28 pages, submitted to STOC 2027

It is well known that $\mathsf{VF} = \mathsf{VBP}_{3}$ (Ben-Or-Cleve'92), i.e. the width of any constant-width algebraic branching program can be reduced to width $3$ with only a polynomial overhead to size. We prove that this is not the case for the monotone equivalents. In particular, we prove that there is an infinite hierarchy $\mathsf{mVBP}_{2} \subsetneq \mathsf{mVBP}_{3} \subsetneq \ldots$ by showing that $\mathrm{imm}_{k,n}$ requires width $w$ mABPs to have depth at least $\left(\frac{k}{w-1}\right)^{\frac{1}{2}\left\lfloor n^{\frac{1}{(w-2)}} \right\rfloor - 1}$ whenever $3 \leq w < k$. We prove this lower bound using support-based techniques. Since this lower bound is exact instead of asymptotic, it allows some width separations even for superconstant width. Moreover, it allows us to show that the expressive power of poly-sized monotone formulas of depth $2d$ is not reached by poly-sized mABPs of width $d-1$ but a width of $2d+1$ is sufficient. We contrast this to unbounded-depth monotone formulas, which are proven to be stronger than constant-width mABPs, but weaker than $\log$-width mABPs and incomparable for most widths in between. Finally, we generalize Snir's framework (Snir'80) for showing lower bounds on the number of leaves of monotone formulas to monotone formulas of multiplication depth $d^{\times}$, giving a lower bound of $n \cdot k^{d^{\times}(n^{\frac{1}{d^{\times}}} - 1)}$ for the iterated matrix multiplication polynomial and $\left(\left(e+o(1)\right) \ln^{\circ(d^{\times}-1)}(n)\right)^n$ for the permanent.

0.32

Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration

cs.LO math.COmath.OC ·2026-10-08 ·Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub
similarity 0.56
Abstract · 20 pages, 3 figures, 2 tables

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

0.28

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.56
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27