CS Paper Radar

RadonBench: A Benchmark of Classical and Learning-Guided Search Techniques for Problems in Combinatorial Geometry

Xiaoan Xu, Jesus A. De Loera, Ethan X. Fang, Junwei Lu, Luze Xu

cs.LG ·submitted 2026-10-23 20:09 UTC · v2
benchmarkunusual

Abstract

Classical optimization and learning-guided search offer complementary approaches to open problems in discrete mathematics, but their outputs are difficult to compare when search spaces, validity checks, and stopping rules differ. We present \emph{RadonBench}, a benchmark for constructing maximum-cardinality Radon-free lattice configurations: finite subsets of $\mathbb{Z}^d$ admitting no integral Radon partition. It remains open whether Radon-free configurations with $11$ points in $\mathbb{Z}^3$ or $21$ points in $\mathbb{Z}^4$ are possible. If they exist, they would improve the corresponding lower bounds on the integer Radon numbers. We compare exhaustive extension, greedy local search, PatternBoost, AlphaZero, and AlphaEvolve. All outputs use one success predicate: a convex target-sized configuration succeeds exactly when its number of integral Radon points is zero. PatternBoost and AlphaZero construct verified Radon-free configurations of sizes $10$ and $20$, one point short of the respective targets; AlphaZero's best convex target terminals have two integral Radon points in both dimensions. Exhaustive extension over fixed seeds and declared finite search boxes likewise reaches a minimum of two integral Radon points. Greedy local search and AlphaEvolve each produce target-sized near misses with one integral Radon point. No audited run reaches zero. These results establish reproducible near-miss baselines over explicitly scoped search domains.

Closest papers

Nearest neighbours by meaning across the whole index.

Five improved lower bounds for Zarankiewicz numbers z(m,n;3,3)

cs.DM math.CO ·2026-08-27 ·Abhishek Saurabh
similarity 0.56
Abstract · 6 pages. Ancillary files: all five witness matrices as bitstrings and JSON, with standalone stdlib-only verifiers (no third-party packages)

We record five improved lower bounds for Zarankiewicz numbers with s = t = 3: z(13,19;3,3) >= 118, z(14,19;3,3) >= 126, z(16,18;3,3) >= 136, z(14,20;3,3) >= 126, z(16,19;3,3) >= 136. The first three are certified by explicit K_{3,3}-free 0/1 matrices; the last two follow from the second and third by monotone padding. Compared with the lower bounds compiled in Figure 2 of arXiv:2605.01120, namely 114, 121, 130, 125 and 132, the improvements are +4, +5, +6, +1 and +4 respectively. The three matrices were produced by a kicked-greedy local search operated autonomously by a discovery system and were verified exactly, by exhaustive inspection of every 3x3 row/column triple, in several mutually independent implementations; they were also re-verified independently by the authors of arXiv:2605.01120 using their own verifier in July 2026. All three witnesses are printed in full in Appendix A and accompany this note as machine-readable ancillary files together with standalone, dependency-free verifiers.

0.31

Integer Programming with Polyhedral Constraints on the Image

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

Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time

cs.DS ·2026-10-09 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.54
Abstract

We give an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for multidimensional subset sum on an explicitly listed multiset of $n$ vectors in $[-N,N]^d$, for every fixed $d$ and $\varepsilon>0$. This directly implies an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for feasibility test of integer programming. Prior to our work, the best-known algorithm has a running time of $O_{d}(n+N^{O(d^2)})$ [Eisenbrand, Weismantel'19]. Specifically, if $d=1$, our algorithm runs in $O_{\varepsilon}(n+N^{1+\varepsilon})$-time for the standard subset sum problem, which is near-linear in the largest input integer. Prior to our work, subset sum can be solved in time near-linear in the target $t$ [Bringmann'17], or near-linear in the mixed parameter $\sqrt{Nt}$ [Chen, Lian, Mao, Zhang'24]. It is a fundamental open problem whether the algorithm can be made near-linear in $N$, which is settled affirmatively in this paper up to an arbitrary small $N^{\varepsilon}$ term.

0.26

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.52
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

Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis

cs.DS ·2026-10-22 ·Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki
top venuetheory similarity 0.52
Abstract · 66 pages, 2 figures, published in FOCS 2026

The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n)}$, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).$M$. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).$M^{1/3}$. In this work, we give the first poly(n).$M^{o(1)}$-time algorithm for Equal Subset Sum in the regime $M = 2^{o(n)}$. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when $M = Θ(2^{n})$: a poly(n)$\cdot 2^{n/4}$-time algorithm in the average case.

0.32

Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study

cs.CG math.CO ·2026-10-14 ·Deepak Ajwani, Paula Carroll, Rishikesh Gajjala, Ananta Manoranjan, Ryan O'Connor +3 more
publishedtheory similarity 0.52
Abstract · Accepted at ALENEX 2027. Abstract compressed to satisfy arxiv guidelines

Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reveal structural sources of computational difficulty. Such constructions, however, are still typically discovered through a slow, manual process. This paper investigates how machine learning can accelerate their discovery to support algorithm design and analysis. We build on PatternBoost, a framework alternating local search with generation from a trained transformer, using its Axplorer implementation to investigate three problems: integrality gaps for maximum independent set of rectangles, integrality gaps for stabbing unit squares with axis-parallel lines, and hard instances for recursive guillotine cutting. By exploring candidate representations, local search operations, and surrogate models used to rank candidates before exact verification, we carefully adapt the framework to these combinatorial geometry problems.While naive representations and search strategies fail to find non-trivial instances, our tailored adaptation discovers numerous non-trivial constructions. For stabbing unit squares, the method reaches a gap of $20/13\approx 1.54$, improving on the literature's best known lower bound of $3/2$. Purely automated search converges rapidly and then plateaus, prompting the question of what is required to push the bound higher still. We find that initial instance diversity plays an important role: with modest expert input via a structured staircase construction, the system reaches an improved integrality gap of $14/9\approx 1.555$. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.

0.38

A Fixed-Parameter Algorithm for 4-Block Integer Programming

cs.CC cs.DS ·2026-09-20 ·Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz
similarity 0.52
Abstract

We give a fixed-parameter tractable (FPT) algorithm with running time $f(k,\barΔ)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute entry $\barΔ$ in the local-column blocks. This result resolves a long-standing open question in parameterized complexity, and answers a conjecture by Eisenbrand and Rothvoss (2026) in the positive. This result has several implications for other block-structured integer programming models, including mixed fracture number and special cases of 4-block programs with large entries outside of the diagonal. Important tools for this algorithm are structural properties of generalized $n$-fold integer programs shown by Ligthart~(2026) and an algorithm by Veselov, Gribanov, Zolotykh and Chirkov~(2020) for optimizing discrete convic functions. Independently and shortly after the first version of our paper appeared, Koutecký, Lassota, and Ligthart (2026) obtained an FPT algorithm for 4-block integer programming.

0.42

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

cs.CC cs.DScs.LG ·2026-09-24 ·Bo Liu
theory similarity 0.52
Abstract · 25 pages, 2 tables; full proof and technical appendix

Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.

0.54