arxiv: 2605.00201 · v1 · submitted 2026-04-30 · 💻 cs.DS · cs.LG

Matroid Algorithms Under Size-Sensitive Independence Oracles

Kiarash Banihashem , MohammadTaghi Hajiaghayi , Mahdi JafariRaviz , Danny Mittal This is my paper

Pith reviewed 2026-05-09 19:41 UTC · model grok-4.3

classification 💻 cs.DS cs.LG

keywords matroidsindependence oraclesquery complexitysize-sensitive costbasis findingrank approximationpartition matroids

0 comments

The pith

Size-sensitive independence oracles force quadratic query cost for matroid basis finding and rank approximation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper replaces the usual constant-time oracle model with one in which each independence query on a set of size k costs time proportional to k. In this model it gives nearly matching upper and lower bounds showing that the three core tasks—constructing a basis, approximating the rank, and approximating the maximum partition size—all require total query cost quadratic in the ground-set size, up to logarithmic factors. The upper bounds are achieved by explicit algorithms; the lower bounds hold even for weaker decision versions of the problems and are unconditional. For the special case of matroids whose circuits are bounded by size c the quadratic barrier can be broken, yielding an expected O(n^{2-1/c} log n) algorithm for maximum-weight basis.

Core claim

We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most c, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost O(n^{2-1/c} log n).

What carries the argument

The size-sensitive independence oracle model, in which the cost of a query Q scales linearly with |Q|.

If this is right

Any algorithm for finding a basis must incur total query cost quadratic in the ground-set size.
Approximating the rank or the size of a maximum partition also requires quadratic cost.
The quadratic bound is tight up to log factors for general matroids.
When every circuit has size at most c the cost for maximum-weight basis drops to O(n^{2-1/c} log n).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same quadratic barrier is likely to appear in other matroid problems whose solutions require many independent-set tests.
Implementations of graphic or linear matroids that already run in near-linear time per query can now be plugged directly into these algorithms without changing the asymptotic cost.
The bounded-circuit-size improvement suggests that circuit-size parameters may yield subquadratic algorithms for additional matroid tasks.

Load-bearing premise

Nearly linear-time implementations of the independence oracle exist for the natural families of matroids to which the model is applied.

What would settle it

A deterministic algorithm that finds a basis using o(n² / polylog n) queries in the size-sensitive model, or a family of matroids where every basis-finding algorithm requires more than O(n² log n) queries.

read the original abstract

The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most $c$, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost $\mathcal{O}(n^{2-1/c} \log n)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces a size-sensitive oracle model that makes quadratic query cost necessary for basic matroid tasks, with matching upper bounds and a parameterized improvement for small circuits.

read the letter

The core point is that under a cost model where each independence query on set Q costs |Q|, the standard matroid problems require quadratic total effort, and the authors give nearly tight bounds plus a way to beat it when circuits are bounded by c. They start from the observation that constant-time oracles hide real work in cases like graphic matroids, where checking a set really takes linear time. The model is backed by the fact that nearly linear-time implementations already exist for many natural matroid families, so the abstraction stays faithful without forcing everyone to implement everything from scratch. They then give explicit algorithms for finding a basis, approximating rank, and approximating partition size that achieve O(n² log n) total cost, and they prove unconditional lower bounds showing that quadratic is necessary even for weaker distinguishing versions of the same problems. The bounded-circuit result stands out: an expected O(n^{2-1/c} log n) algorithm for maximum-weight basis. That part is constructive and breaks the quadratic barrier in a clean parameterized way. The lower bounds do not rely on reductions that loop back to the same parameters, and the upper bounds come from concrete procedures rather than non-constructive arguments. A minor soft spot is that the practical tightness still depends on how cleanly those nearly linear oracles can be implemented in code for the matroids people actually use; the abstract does not show runtime measurements or data-structure details that would confirm no hidden overhead creeps in. The lower bounds are worst-case and might leave faster options open for average-case or highly structured families. This work is for people who design or analyze matroid algorithms in combinatorial optimization, network reliability, or feature selection. A reader who already thinks about oracle cost models will find the framework and the explicit bounds useful. The thinking is clear and the claims line up with the stated model, so it deserves a serious referee even if some implementation details need more space in revision.

Referee Report

2 major / 3 minor

Summary. The manuscript introduces a size-sensitive independence oracle model for matroids in which the cost of an independence query on a set Q is |Q|. Within this model, the authors study three fundamental problems: computing a basis, approximating the rank, and approximating the partition size. They prove nearly matching upper and lower bounds establishing that the optimal query complexity is quadratic in the matroid size, up to logarithmic factors. The upper bounds are achieved via explicit algorithmic procedures, while the lower bounds are unconditional and apply even to weaker distinguishing variants of the problems. Additionally, they present an algorithm that breaks the quadratic barrier for matroids with maximum circuit size bounded by a constant c, achieving expected query cost O(n^{2-1/c} log n) for the maximum-weight basis problem.

Significance. If the results hold, this work is significant for refining the standard constant-time oracle model into one that better reflects real computational costs, especially for natural matroid classes such as graphic matroids. The nearly tight quadratic bounds provide a clear complexity characterization in the new model, the explicit upper-bound constructions and unconditional lower bounds strengthen the claims, and the improved algorithm for bounded-circuit matroids illustrates how structural restrictions can yield better performance. These elements could influence future analyses of matroid algorithms in combinatorial optimization.

major comments (2)

[§2] §2 (model definition): The statement that nearly linear-time oracle implementations exist for broad families of matroids is load-bearing for the claim that the size-sensitive model faithfully captures true effort; a concrete reference or short argument for at least one important family (e.g., graphic matroids) should be supplied.
[Lower-bound section] Lower-bound section (around the distinguishing formulations): The reduction from the distinguishing versions to the approximation tasks must be spelled out explicitly, because the tightness claim rests on these lower bounds applying to the original problems.

minor comments (3)

[Abstract] Abstract: the approximation ratios achieved for rank and partition size are not stated; they should be given explicitly.
[Throughout] Notation: confirm that the ground-set size is uniformly denoted by n throughout the algorithms and complexity statements.
[Introduction / Conclusion] The final algorithm for bounded-circuit matroids is stated only in the abstract; a short high-level description of the technique should appear in the introduction or conclusion for readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the constructive comments. We address each major comment below and will incorporate the requested clarifications into the revised manuscript.

read point-by-point responses

Referee: [§2] §2 (model definition): The statement that nearly linear-time oracle implementations exist for broad families of matroids is load-bearing for the claim that the size-sensitive model faithfully captures true effort; a concrete reference or short argument for at least one important family (e.g., graphic matroids) should be supplied.

Authors: We agree that an explicit example strengthens the motivation. For graphic matroids, an independence query on a set Q of edges can be answered via Union-Find with path compression and union-by-rank in O(|Q| α(n)) time, where α is the inverse Ackermann function (effectively constant). We will insert a short paragraph in §2 with this argument and a reference to standard Union-Find implementations. revision: yes
Referee: [Lower-bound section] Lower-bound section (around the distinguishing formulations): The reduction from the distinguishing versions to the approximation tasks must be spelled out explicitly, because the tightness claim rests on these lower bounds applying to the original problems.

Authors: We thank the referee for this observation. The lower bounds are proven for the distinguishing formulations (weaker variants). We will explicitly spell out the reduction: any algorithm for the approximation task yields an algorithm for the corresponding distinguishing task with only constant-factor overhead in query cost. This transfers the lower bounds directly to the original approximation problems and will be added to the lower-bound section. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines a size-sensitive oracle model with query cost exactly |Q| and derives its main results via explicit algorithmic constructions for the upper bounds on basis finding, rank approximation, and partition size approximation, together with unconditional lower bounds that apply even to weaker distinguishing versions of the problems. These bounds are obtained by direct analysis of the procedures and standard complexity arguments within the model; no step reduces a claimed prediction or theorem to a fitted parameter, self-citation chain, or definitional renaming. The special-case algorithm for bounded circuit size is likewise presented as a new construction that improves the general quadratic bound. The derivation chain is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the newly introduced size-sensitive cost model plus standard matroid axioms; no free parameters are fitted to data and no new physical entities are postulated.

axioms (2)

standard math Matroids satisfy the standard independence axioms (hereditary property and augmentation property).
Invoked throughout as the background structure on which the new cost model is defined.
domain assumption Independence queries can be answered in time linear in the size of the queried set for broad families of matroids.
This is the key modeling assumption that justifies replacing the constant-time oracle with the size-sensitive one.

invented entities (1)

Size-sensitive independence oracle no independent evidence
purpose: To assign query cost proportional to set cardinality instead of constant time.
New abstraction introduced to close the gap between theoretical and practical matroid algorithms.

pith-pipeline@v0.9.0 · 5606 in / 1499 out tokens · 43639 ms · 2026-05-09T19:41:40.718915+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 5 canonical work pages

[1]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

A fast approximation for maximum weight matroid intersection , author=. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2016 , organization=

2016
[2]

Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

Breaking the quadratic barrier for matroid intersection , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=
[3]

Deterministic

Terao, Tatsuya , journal =. Deterministic
[4]

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Faster exact and approximation algorithms for packing and covering matroids via push-relabel , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

2024
[5]

Transversals and matroid partition , author=. J. Res. Nat. Bur. Standards Sect. B , volume=
[6]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

Fast algorithms via dynamic-oracle matroids , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=
[7]

International Conference on Machine Learning , pages=

Fully dynamic submodular maximization over matroids , author=. International Conference on Machine Learning , pages=. 2023 , organization=

2023
[8]

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Dynamic algorithms for matroid submodular maximization , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

2024
[9]

2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

A faster cutting plane method and its implications for combinatorial and convex optimization , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

2015
[10]

arXiv preprint arXiv:2507.08194 , year=

On the Parallel Complexity of Finding a Matroid Basis , author=. arXiv preprint arXiv:2507.08194 , year=

work page arXiv
[11]

Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

Matroid prophet inequalities , author=. Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=
[12]

Proceedings of the twelfth annual ACM symposium on Theory of computing , pages=

Random matroids , author=. Proceedings of the twelfth annual ACM symposium on Theory of computing , pages=
[13]

2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Faster matroid intersection , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

2019
[14]

2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

2024
[15]

Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms , pages=

Prophet secretary for combinatorial auctions and matroids , author=. Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms , pages=. 2018 , organization=

2018
[16]

Journal of the ACM (JACM) , volume=

Matroid secretary problems , author=. Journal of the ACM (JACM) , volume=. 2018 , publisher=

2018
[17]

20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , pages=

Efficient algorithms for simple matroid intersection problems , author=. 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , pages=. 1979 , organization=

1979
[18]

Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=

Forests, frames, and games: algorithms for matroid sums and applications , author=. Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=
[19]

Journal of Algorithms , volume=

Algorithms for graphic polymatroids and parametrics-sets , author=. Journal of Algorithms , volume=. 1998 , publisher=

1998
[20]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

2025
[21]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

Dynamic o (arboricity) coloring in polylogarithmic worst-case time , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=
[22]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

Faster sublinear approximation of the number of k-cliques in low-arboricity graphs , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

2020
[23]

ACM Transactions on Algorithms (TALG) , volume=

Testing bounded arboricity , author=. ACM Transactions on Algorithms (TALG) , volume=. 2020 , publisher=

2020
[24]

SIAM Journal on Computing , volume=

Improved bounds for matroid partition and intersection algorithms , author=. SIAM Journal on Computing , volume=. 1986 , publisher=

1986
[25]

Matroid Semi-Bandits in Sublinear Time , booktitle =

Ruo. Matroid Semi-Bandits in Sublinear Time , booktitle =. 2024 , url =

2024
[26]

Fully Dynamic Submodular Maximization over Matroids , booktitle =

Paul Duetting and Federico Fusco and Silvio Lattanzi and Ashkan Norouzi. Fully Dynamic Submodular Maximization over Matroids , booktitle =. 2023 , url =

2023
[27]

Accelerating Matroid Optimization through Fast Imprecise Oracles , booktitle =

Franziska Eberle and Felix Hommelsheim and Alexander Lindermayr and Zhenwei Liu and Nicole Megow and Jens Schl. Accelerating Matroid Optimization through Fast Imprecise Oracles , booktitle =. 2024 , url =

2024
[28]

Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits , booktitle =

Orestis Papadigenopoulos and Constantine Caramanis , editor =. Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits , booktitle =. 2021 , url =

2021
[29]

Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time , booktitle =

Kai Han and Zongmai Cao and Shuang Cui and Benwei Wu , editor =. Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time , booktitle =. 2020 , url =

2020
[30]

Deletion Robust Submodular Maximization over Matroids , booktitle =

Paul Duetting and Federico Fusco and Silvio Lattanzi and Ashkan Norouzi. Deletion Robust Submodular Maximization over Matroids , booktitle =. 2022 , url =

2022
[31]

Thirty-Fifth

Nawal Benabbou and Cassandre Leroy and Thibaut Lust and Patrice Perny , title =. Thirty-Fifth. 2021 , url =. doi:10.1609/AAAI.V35I14.17452 , timestamp =

work page doi:10.1609/aaai.v35i14.17452 2021
[32]

Thirty-Sixth

Siddharth Barman and Paritosh Verma , title =. Thirty-Sixth. 2022 , url =. doi:10.1609/AAAI.V36I5.20407 , timestamp =

work page doi:10.1609/aaai.v36i5.20407 2022
[33]

Submodular Maximization under the Intersection of Matroid and Knapsack Constraints , booktitle =

Yu. Submodular Maximization under the Intersection of Matroid and Knapsack Constraints , booktitle =. 2023 , url =. doi:10.1609/AAAI.V37I4.25510 , timestamp =

work page doi:10.1609/aaai.v37i4.25510 2023
[34]

A Matroid Approach to the Worst Case Allocation of Indivisible Goods , booktitle =

Laurent Gourv. A Matroid Approach to the Worst Case Allocation of Indivisible Goods , booktitle =. 2013 , url =

2013
[35]

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence,

Yu Cong and Chao Xu and Yi Zhou , title =. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence,. 2025 , url =. doi:10.24963/IJCAI.2025/287 , timestamp =

work page doi:10.24963/ijcai.2025/287 2025
[36]

18th Annual Symposium on Foundations of Computer Science (sfcs 1977) , pages=

Probabilistic computations: Toward a unified measure of complexity , author=. 18th Annual Symposium on Foundations of Computer Science (sfcs 1977) , pages=. 1977 , organization=

1977