Recognition: unknown
Faster Approximate Linear Matroid Intersection
Pith reviewed 2026-05-10 14:47 UTC · model grok-4.3
The pith
A (1-ε)-approximation algorithm for linear matroid intersection runs in Õ_ε(nnz(M1) + nnz(M2) + r_* ^ω) time.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We design a (1 - ε)-approximation algorithm with time complexity Õ_ε(nnz(M1) + nnz(M2) + r_* ^ω) for linear matroid intersection and the same bound for the weighted version by combining Quanrud's adaptive sparsification framework with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors.
What carries the argument
Quanrud's adaptive sparsification framework combined with a fast linear-span membership test that avoids full matrix operations on every query.
If this is right
- The same time bound holds for the weighted linear matroid intersection problem.
- The algorithm improves on Harvey's exact algorithm and on Cheung-Kwok-Lau's exact algorithm, both of which require an extra n r_* ^{ω-1} term.
- It improves on Huang-Kakimura-Kamiyama's (1-ε)-approximation algorithm, which also carries the n r_* ^{ω-1} term.
- The running time becomes near-linear in the input sparsity plus a single matrix-multiplication cost on the output rank.
Where Pith is reading between the lines
- When r_* is much smaller than n the algorithm becomes substantially faster than all prior methods and may be practical for large sparse instances.
- The span test may be reusable in other dynamic or iterative linear-algebra settings that repeatedly ask membership queries.
- The approach could be adapted to other matroid intersection variants that admit similar sparsification.
Load-bearing premise
The new linear-span membership test integrates with adaptive sparsification without introducing extra logarithmic or polynomial factors beyond the claimed bound.
What would settle it
An input family of matrices for which the span-membership tests required by the sparsification procedure take more than O(r_* ^ω) total time or push the overall running time above Õ_ε(nnz(M1) + nnz(M2) + r_* ^ω).
read the original abstract
We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two $r \times n$ matrices $M_1$ and $M_2$, and the objective is to find a largest set of columns that are linearly independent in both $M_1$ and $M_2$. We design a $(1 - \varepsilon)$-approximation algorithm with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + r_{*}^{\omega})$, where $\mathrm{nnz}(M_i)$ denotes the number of nonzero entries in $M_i$ for $i = 1, 2$, $r_{*}$ denotes the maximum size of a common independent set, and $\omega < 2.372$ denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS'06 & SICOMP'09] and Cheung--Kwok--Lau [STOC'12 & JACM'13], which runs in $\tilde{O}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + n r_{*}^{\omega - 1})$ time. We also develop a fast $(1 - \varepsilon)$-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a $(1 - \varepsilon)$-approximation algorithm for weighted linear matroid intersection with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + r_{*}^{\omega})$. Our algorithm improves upon the $(1 - \varepsilon)$-approximation algorithm by Huang--Kakimura--Kamiyama [SODA'16 & Math. Program.'19], which runs in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + nr_{*}^{\omega - 1})$ time. To obtain these results, we combine Quanrud's adaptive sparsification framework [ICALP'24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims a (1-ε)-approximation algorithm for linear matroid intersection on two r×n matrices M1 and M2, achieving runtime Õ_ε(nnz(M1)+nnz(M2)+r_* ^ω) where r_* is the size of the maximum common independent set. It extends the same bound to the weighted case. The algorithm combines Quanrud's adaptive sparsification framework (ICALP'24) with a new subroutine for efficient linear-span membership testing; this is asserted to improve on Harvey's exact algorithm and on Huang-Kakimura-Kamiyama's (1-ε)-approximation, both of which retain an extra n r_* ^{ω-1} factor.
Significance. If the claimed runtime holds, the result would be a substantial improvement in the field of matroid algorithms, replacing the n-dependent term with a dependence only on the output size r_* plus matrix-multiplication time. The new span-membership primitive is presented as independently useful. The paper supplies no machine-checked proofs or reproducible code, but the asymptotic improvement is falsifiable via implementation on dense instances.
major comments (2)
- [Abstract / Technique paragraph] Abstract and technique paragraph: the central runtime claim Õ_ε(nnz(M1)+nnz(M2)+r_* ^ω) rests on the assertion that the new span-check subroutine integrates with Quanrud's adaptive sparsification without incurring more than Õ_ε(r_* ^ω) total cost. No explicit count of membership queries per phase, no amortized per-query complexity, and no error analysis showing that the (1-ε) guarantee is preserved under the combination are supplied; if each of the Θ(r_*) candidate vectors per phase triggers an independent Ω(r^ω) operation, the product exceeds the stated bound.
- [Abstract] No section or equation is given that bounds the total number of span-membership tests across all phases of adaptive sparsification or shows that the preprocessing makes each test o(r^ω) amortized. The claim that the combination yields the stated runtime is therefore load-bearing but unsupported in the provided text.
Simulated Author's Rebuttal
We thank the referee for their detailed and constructive feedback on our submission. We address each major comment below. We agree that the abstract and technique paragraph would benefit from additional explicit bounds and will revise the manuscript to incorporate them.
read point-by-point responses
-
Referee: [Abstract / Technique paragraph] Abstract and technique paragraph: the central runtime claim Õ_ε(nnz(M1)+nnz(M2)+r_* ^ω) rests on the assertion that the new span-check subroutine integrates with Quanrud's adaptive sparsification without incurring more than Õ_ε(r_* ^ω) total cost. No explicit count of membership queries per phase, no amortized per-query complexity, and no error analysis showing that the (1-ε) guarantee is preserved under the combination are supplied; if each of the Θ(r_*) candidate vectors per phase triggers an independent Ω(r^ω) operation, the product exceeds the stated bound.
Authors: We agree that the abstract and technique paragraph lack an explicit accounting of query counts and amortization. In the revised version we will expand the technique paragraph to state that adaptive sparsification performs O(r_*/ε) phases in total, that our span-check subroutine is invoked O(1) times per candidate vector per phase, and that preprocessing reduces the amortized cost per test to o(r^ω) via fast rectangular matrix multiplication, yielding the claimed Õ_ε(r_* ^ω) bound overall. We will also add a short paragraph confirming that the (1-ε) guarantee is preserved because the sparsification framework only requires correct (not approximate) span checks and our subroutine returns exact answers. revision: yes
-
Referee: [Abstract] No section or equation is given that bounds the total number of span-membership tests across all phases of adaptive sparsification or shows that the preprocessing makes each test o(r^ω) amortized. The claim that the combination yields the stated runtime is therefore load-bearing but unsupported in the provided text.
Authors: The referee correctly notes the absence of such a bounding equation or section reference in the abstract. We will revise the abstract's technique paragraph to include a high-level equation summarizing the total number of tests (Õ_ε(r_*)) and the amortized per-test cost after preprocessing. The supporting lemmas and proofs already appear in Sections 3–5 of the body; the revision will simply make the abstract self-contained by citing the relevant theorem numbers and sketching the amortization argument. revision: yes
Circularity Check
No circularity: algorithmic construction relies on external framework plus novel subroutine
full rationale
The paper derives its runtime bound by combining Quanrud's adaptive sparsification (external citation, ICALP'24) with a new linear-span membership test subroutine presented as independently interesting. No equations reduce the output runtime or approximation ratio to a fitted parameter or self-defined quantity. No self-citations appear in the provided text, and the central claim does not invoke uniqueness theorems or ansatzes from prior author work. The derivation is self-contained against external benchmarks and does not exhibit any of the enumerated circular patterns.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Matrix multiplication of n × n matrices can be performed in O(n^ω) time for ω < 2.372
Forward citations
Cited by 1 Pith paper
-
Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
A new coordinatewise balanced covering theorem for linear gain graphs yields a randomized algorithm for Coset-List Min-2-Lin over powers of two with runtime exponential in k squared times the cycle-label rank rho.
Reference graph
Works this paper leans on
-
[1]
38 Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann
Preliminary version in SODA 2016.doi:10.1007/s10107-018-1260-x. 38 Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann. Rank-profile revealing gaussian elimination and the cup matrix decomposition.Journal of Symbolic Computation, 56:46–68, 2013.doi:10.1016/j.jsc.2013.04.004. 39 Tomohiro Koana and Magnus Wahlström. Faster algorithms on linear delt...
-
[2]
44 Rajeev Motwani and Prabhakar Raghavan.Randomized Algorithms
Preliminary version in IPCO 2021.doi:10.1137/21m1421751. 44 Rajeev Motwani and Prabhakar Raghavan.Randomized Algorithms. Cambridge University Press, 1995.doi:10.1017/cbo9780511814075. 45 Harihar Narayanan, Huzur Saran, and Vijay V Vazirani. Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjo...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.