CS Paper Radar

Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids

Robert P. Streit

cs.DM math.CO ·submitted 2026-11-11 17:34 UTC · v1
theory

Abstract

For a regular matroid on $m$ elements with positive weights and weighted girth $g_w$, we prove that the number of circuits of weight at most $αg_w$ is bounded by $(Km)^{2α}$, for every real $α\ge1$ and an absolute constant $K$. This improves the previous $m^{O(α^2)}$ bound of Gurjar and Vishnoi and matches classic graph cut and cycle counting bounds of Karger and Subramanian. We also show this is asymptotically optimal for all real $α\geq 1$ under the Erdős girth conjecture, while unconditional optimality holds for half-integer $α$ by prior results. As consequences, we resolve a recent conjecture by Khanna, Putterman, and Song implying the existence of a parallel basis search algorithm for regular matroids terminating in logarithmically many rounds of independence queries, and obtain improved bounds on the number of near-minimum weight codewords in regular codes and near-shortest vectors in totally unimodular lattices under $\ell_p$-norms.

Comment
28 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Almost entropic matroids and $(k,L)$-systems

cs.IT math.CO ·2026-10-20 ·Andrey Kupavskii, Nikolai Terekhov
theory similarity 0.72
Abstract

For an integer $k$ and a set of integers $L$, a $(k,L)$-system is a family of $k$-element sets such that the size of the intersection of any two distinct members belongs to $L$. Let $m(n,k,L)$ denote the maximum size of a $(k,L)$-system on a ground set of $n$ elements. In this work, we establish a close connection between the asymptotic growth of $m(n,k,L)$ and almost entropic matroids. As a consequence, we obtain a general computable upper bound on the asymptotics of $m(n,k,L)$ that unifies and strengthens all previously known upper bounds.

0.48

Random Deletion for Circuits in Regular Matroids

cs.DS ·2026-10-24 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
similarity 0.71
Abstract · 43 pages, 5 figures

We study a simple random deletion algorithm to find short circuits in regular matroids. Given a regular matroid $M$ with $m$ elements, the algorithm randomly deletes each element independently with probability $1-1/m^{Θ(1/g)}$ where $g$ is the size of a minimum circuit, and returns the remaining set $R$ of elements. We establish the following results: 1. With high probability, $R$ contains no circuit and is therefore independent. 2. For every $α$-approximate minimum circuit $C$ where $α\geq 1$, with probability at least $m^{-O(α)}$, the entire circuit $C$ survives in $R$ and moreover, the minimum number of elements that need to be removed to make $R$ independent is $O(α\log(α+2))$. This yields an algorithmic proof that the number of $α$-approximate minimum circuits is $m^{O(α)}$, improving the previous known bound of $m^{O(α^2)}$ by Gurjar and Vishnoi, and resolving a recent conjecture of Khanna, Putterman, and Song. Our results yield two immediate applications. First, we obtain very simple RNC algorithms for computing the shortest circuit, and for enumerating all $α$-approximate circuits, of a regular matroid without computing the Seymour decomposition. Second, we obtain a randomized parallel algorithm to find a basis of a regular matroid under independence-oracle access. It uses polynomially many independence-oracle queries in $O(\log m)$ adaptive rounds and succeeds with high probability. This follows from the framework of Khanna, Putterman, and Song and the improved counting bound, and extends their result from graphic matroids to regular matroids.

0.61

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.70
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Derandomizing Karger's Contraction Algorithm for Matroids

cs.DS cs.DMmath.CO ·2026-08-17 ·Yu Cong, Chao Xu, Yajie Zhao
theory similarity 0.69
Abstract

Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a deterministic algorithm with the same exponent. If every contraction minor of rank at least $r_0$ of a matroid $M$ has cogirth-density ratio at most $c$, then a minimum-weight cocircuit of $M$ is computable deterministically in $m^{O(r_0)} n^{O(c)}$ time when the contraction minors of bounded rank have at most $m$ parallel classes, by an algorithm that knows neither $r_0$ nor $c$. As a consequence, we give a deterministic algorithm computing the cogirth of rank-$p$ perturbed graphic matroids in $2^{O(p^2)} n^{O(1)}$ time, fixed-parameter tractable in $p$, settling the cogirth side of a question of Geelen and Kapadia (2018). The extensions of the contraction method carry over deterministically: enumerating all near-minimum 1-cocycles, computing a minimum-weight $k$-cocycle, and computing the Pareto frontier under several positive criteria.

0.36

Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases

cs.DS math.CO ·2026-10-23 ·Siyue Liu, Taihei Oki, Chao Xu
theory similarity 0.69
Abstract

Let $M$ be a matroid, let $\ell:E(M)\to G$ be a labeling of its elements by an abelian group, and let $F\subseteq G$ be finite. A base is $F$-avoiding if the label sum of its elements is not in $F$. We prove that, for arbitrary costs, a min-cost $F$-avoiding base can be obtained from any min-cost base using at most $|F|$ exchanges. This resolves the weighted proximity conjecture by Hörsch, Imolay, Mizutani, Oki, and Schwarcz. Our main technical tool is to replace the assumption of Schrijver--Seymour Conjecture in Liu and Xu's earlier work with Kemperman--Scherk Theorem. The proximity theorem combined with approaches in earlier work gives an FPT algorithm that finds a min-cost $F$-avoiding base parameterized by $|G|$. We additionally give an FPT algorithm parameterized by $|F|$, answering a question of Hörsch et al.

0.29

Logarithmic basis number of graphs and regular matroids

cs.DM math.CO ·2026-09-02 ·Kolja Knauer
theory similarity 0.68
Abstract · 13 pages

The basis number $bn(G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$-vertex multigraph satisfies $bn(G)=O(\log n)$, resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement $bn(G)=O(\log β(G))$, where $β(G)$ is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives $bn(G)=O(\log g)$ for graphs of Euler genus $g$. For regular matroids we prove the ground-set bound $bn(M)=O(\log m)$, where $m=|E(M)|$, and logarithmic bounds in both the rank $r(M)$ and the cycle-space dimension $d$. All these orders are best possible.

0.51

Quadratic bounds for uncompletable words and matrix mortality

cs.FL math.CO ·2026-09-25 ·Rahul Chandelkar, Samrath Singh Chadha
similarity 0.66
Abstract · Lean formalization and implementation pilot included as ancillary material

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

0.32

CPM-LDPC Codes Attaining the Minimum-Distance Bound

cs.IT ·2026-09-15 ·Kenta Kasai
theorycode/data similarity 0.66
Abstract · 13 pages, 1 figure, 2 tables. Verification code and data: https://github.com/kasaikenta/cpm-ldpc-distance

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\ldots,8$, and arrays with distance at least 28 for $J=4$, $L=5,\ldots,8$, together with computational distance verification.

0.52