Pith. sign in

REVIEW 3 major objections 5 minor 59 references

Linear Matroid Intersection is in Catalytic Logspace

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Linear matroid intersection can be solved in catalytic logspace

desk verdict Linear matroid intersection in CLP is a genuinely new barrier result, but the proof has a load-bearing gap in Lemma 2.17's use of a weighted-matching subroutine not present in the cited AM25 work. read the letter →

arxiv 2509.06435 v2 pith:XJUHCUNB submitted 2025-09-08 cs.CC

Aryan Agarwala , Yaroslav Alekseev , Antoine Vinciguerra This is my paper · ORCID
classification cs.CC
keywords catalyticlogspacelinearmatroidintersectionisolationlemmaexchangegraphcompressionanddecompressionspaceCLPderandomization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that linear matroid intersection, the problem of finding a largest common independent set of two linear matroids, is solvable in catalytic logspace with polynomial time (CLP). This is the first sublinear free-space, polynomial-time algorithm for the problem, and it places linear matroid intersection as the hardest known problem inside CL. If correct, it strengthens the barrier against the conjecture that CL is contained in the NC hierarchy, and gives a derandomization of the isolation lemma for linear matroid intersection in CLP.

What carries the argument

The exchange graph of the two matroids with respect to an isolated common independent set Ik, together with inclusion and exclusion matroids that restrict whether a threshold element s belongs to the set. If the current weights do not isolate a size-k+1 common independent set, a threshold element s exists; the weight of s can be recovered from the difference between the minimum weight of a size-k+1 common independent set containing s (expressed through the inclusion matroid) and one excluding s (expressed through the exclusion matroid). Minimum-weight minimum-hop cycles through s in the exchange graph give these values, and the catalytic tape is compressed by swapping s's weight with a reserve weight whose position now stores s, k, and a bit b. Decompression recomputes s's weight from the stored data and swaps it back.

What would settle it

Check whether a catalytic logspace machine can compute a minimum-weight perfect matching in a general directed graph with vertex weights; if the matching subroutine only computes unweighted maximum matchings and cannot be modified to return minimum-weight objects, the cycle computations in Lemma 2.17 and the subsequent compression-decompression steps would lose their foundation.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: Linear Matroid Intersection is in CLP. Concretely, Theorem 2.5 states that given two linear matroids by their linear representations, a catalytic Turing machine with O(log n) work space and poly(n) catalytic space can output a maximum common independent set and restore the catalytic tape to its original state. Combined with the known result CLP = CL ∩ P, this upgrades to polynomial time. The proof derandomizes the isolation lemma for linear matroid intersection, extending the approach Agarwala and Mertz used for bipartite matching, by maintaining a weight assignment on the catalytic tape that isolates a unique minimum-weight common independent set of each size, and using a compress-and-decompress scheme to handle weights that fail to isolate the next size.

Load-bearing premise

The proof relies on the catalytic matching algorithm of Agarwala and Mertz being able to compute a minimum-weight perfect matching, not just a maximum-cardinality one, because the cycle-finding and threshold-detection steps in the exchange graph use weighted matching as a black box.

Editorial extensions

If this is right

  • Linear matroid intersection is the hardest problem known to be solvable in CL, strengthening the barrier against the conjecture CL ⊆ NC.
  • The isolation lemma for linear matroid intersection is derandomized in CLP, giving a sublinear free-space and polynomial-time algorithm without additional randomness or nondeterminism.
  • All special cases of linear matroid intersection, including bipartite matching, rainbow spanning tree, and edge-disjoint spanning trees, are now solvable in CLP.
  • The catalytic compress-or-random framework is extended from bipartite matching to a substantially more general combinatorial optimization problem.
  • Any improvement to the exchange-graph cycle-finding subroutine or the underlying catalytic matching subroutine would directly transfer to this algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the catalytic matching subroutine can be strengthened to handle non-bipartite matching, the same proof structure might extend to linear matroid parity, which generalizes non-bipartite matching and is a natural next target.
  • The compression-decompression scheme suggests a generic template for derandomizing isolation lemmas inside CLP whenever the optimal solutions form an exchange-graph-like structure with short certificates.
  • A possible testable consequence is that any future result placing a problem that contains linear matroid intersection into CL would need to use a mechanism beyond the current exchange-graph cycle analysis, because this algorithm already captures a maximal class for that technique.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper claims to prove that Linear Matroid Intersection (LMI) can be solved in catalytic logspace with polynomial time (CLP), by exhibiting a CL algorithm and appealing to the known theorem CLP = CL ∩ P. The algorithm follows the compress-or-random framework: the catalytic tape stores a weight assignment W; as long as W isolates a minimum-weight common independent set of each size, the isolated set is computed and output. When W fails to isolate a size k+1 set, the algorithm finds a threshold element s, compresses the weight of s into a reserve slot, and later decompresses it by computing two matroid minima (inclusion and exclusion) whose difference recovers w(s). After polynomially many compressions, enough free catalytic space is available to run Edmonds' polynomial-time algorithm, and the tape is restored. The main technical novelty is the use of inclusion/exclusion matroids and exchange graphs to compute the quantities needed for threshold detection and decompression.

Significance. If the proof can be completed, this is a significant advance: LMI generalizes bipartite matching, so the result would place the hardest known problem in CLP, strengthen the barrier against CL ⊆ NC, and provide a catalytic derandomization of the isolation lemma for LMI. The high-level architecture is coherent, and the compression invariant (recover w(s) as b − a from inclusion and exclusion matroid minima) is sound. The paper is not circular: it reduces LMI to prior results on bipartite matching, matroid intersection, exchange graphs, and catalytic class structure, none of which assume the target theorem. However, two load-bearing subroutine statements are not currently justified, so the main theorem is not yet established as written.

major comments (3)
  1. [Appendix A, proof of Lemma (Theorem 2.17)] The proof constructs a bipartite graph G′ and states: "We then compute the minimum weight perfect matching M of G′ using [AM25]." The paper's own abstract and Section 1.1 describe [AM25] only as a CLP algorithm for maximum bipartite matching; no statement in the manuscript establishes that [AM25] computes minimum-weight perfect matchings. This is load-bearing: Lemma 2.17 is the only primitive that produces a minimum-weight minimum-hop cycle through a specified vertex, and it is used in Lemmas 5.8, 5.9, and 6.2 for threshold detection and for decompressing w(s). If [AM25] does not supply a catalytic min-weight perfect matching algorithm, the cycle computations lose their foundation and the compression–decompression scheme collapses as written. Please either cite and state the exact weighted matching result in [AM25] (including its handling of possibly negative weights), or replace Lemma 2.17 with a direct CL algorithm based on Lemmas 2.14–2.16 (with the range issue in the next comment fixed), or prove the needed min-weight perfect matching capability from first principles.
  2. [Section 2.3, Lemmas 2.15–2.16, and their use in Lemmas 4.4 and 5.7] Lemma 2.16 is stated only for vertex weights l:V→Z≤poly(n), i.e., non-negative weights, and its algorithm iterates L from 0 upward to ∑_{v∈V} l(v). However, the exchange graph E_{M1,M2,I} defined in Definition 4.1 assigns l(s)=−W(s) to elements of I, so its vertex weights are not non-negative; ∑ l(v) can be negative even when every X1−X2 path has non-negative weight (as is the case when I is a minimum-weight size-k common independent set). Consequently, the iteration in Lemma 2.16 can terminate before the true minimum path weight is reached, and Lemma 5.7's computation of min_{k+1}(M1,M2) is not justified as written. The same issue affects the use of Theorem 2.16 for path existence in Lemma 4.4. This is repairable by iterating L over a symmetric polynomial range (e.g., [−nB, nB] for B = max|W|) and by proving that the relevant path weights are non-negative, but the statement and proof need to be corrected.
  3. [Section 6, proof of Theorem 6.3] After running Edmonds' polynomial-time algorithm A in the free space created by compression, the catalytic tape is no longer of the form (w′,r′,τ) required by the Decomp procedure: A may overwrite the zeroed leading bits of the compressed reserve blocks, and the final section τ may have been used. The proof does not explain how the tape is returned to the exact form needed for decompression before the iterative loop over j. In particular, the metadata bits (s,k,b) in each r′_j must be preserved while A runs, and the free bits must be re-zeroed (or otherwise restored) before Decomp is invoked. This is part of the catalytic restoration guarantee, so it needs to be stated and argued explicitly.
minor comments (5)
  1. [Section 5.3 and proof of Lemma 5.10] Lemma 5.9 is referred to as "Theorem 5.9" in several places, and Lemmas 3.4 and 3.5 are cited as "Theorem 3.4" and "Theorem 3.5"; the numbering and cross-referencing should be harmonized.
  2. [Definition 2.10] The definition of the exclusion matroid contains a typographical error: "{I∈I|s /∈I)" should have a closing brace, and the weights should be written as w restricted to S\{s}.
  3. [Appendix A, proof of Lemma 3.3] The uniqueness argument invokes "Claim 3.4 in [AM25]" without stating the claim; since this claim is essential for the proof that the minimum-weight perfect common independent set is unique, please either state it in full or give a self-contained proof (the lexicographically minimal extension E* is standard but should be made precise).
  4. [Section 6.1, Lemma 6.1] The compressed reserve format is r′=(0^{8 log|S|−1},s,k,b), so the number of leading zero bits is 8 log|S|−1, not "more than 7 log n" as written in the proof of Theorem 6.3; please align these descriptions.
  5. [Throughout] There are several typographical errors, including "of of" in Section 1.5, "explicitly" for "explicitly" in Section 2.1, and "containings" for "containing s" in the appendix; these should be corrected in a final polish.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof reduces LMI to external matching, exchange-graph, and class-structure primitives; the [AM25] weighted-matching dependency is a technical gap, not a circular reduction.

full rationale

The derivation chain is not circular in the forbidden sense: the target result (Linear Matroid Intersection in CLP) is never assumed as an input. Theorem 1.1/2.5 is obtained by (i) proving LMI in CL via an isolation-lemma/compress-or-decompress argument, and (ii) invoking CLP = CL ∩ P from [CLMP25], an external class-structure result. Inside the CL proof, every subroutine is justified by standard or previously established facts: membership testing for linear matroids in TC1 ⊆ CL; the [NSV94] isolation-based algorithm; exchange-graph augmentation lemmas from Edmonds/Schrijver; and Agarwala–Mertz [AM25] as a catalytic bipartite matching primitive. None of these facts assume LMI ∈ CLP or this paper's Theorem 1.1. The one author-overlap citation, [AM25], is used as an external primitive (bipartite matching), not as a source of the matroid-intersection conclusion. Even the Appendix statement 'We then compute the minimum weight perfect matching M of G′ using [AM25]' does not make the argument circular; it raises a correctness/technical-support question, because the paper's own abstract attributes to [AM25] a maximum-cardinality matching algorithm, not a minimum-weight one. An unstated premise of that kind is a gap to be checked, not a self-referential derivation. No equation is defined in terms of its own conclusion, and no fitted quantity is renamed as a prediction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard catalytic complexity inclusions, on textbook exchange graph theorems, and on a specific unstated capability of the Agarwala-Mertz matching algorithm to produce minimum-weight perfect matchings. No data fitting or invented entities are involved.

assumptions (5)
  • domain assumption Composite CL algorithms can be run sequentially on a shared catalytic tape, each restoring the tape to its pre-call state.
    The final algorithm composes many CL subroutines such as Theorems 3.4, 4.4, 5.10, Comp, and Decomp, each of which assumes it may use and restore the whole catalytic tape.
  • standard math TC1 subset CLP and NL subset CL, as shown by Buhrman et al.
    Invoked in Lemmas 2.12, 2.16, and 3.2 for matrix rank, determinant, and reachability subroutines.
  • domain assumption CLP equals CL intersect P, as stated in Theorem 2.4 from Cook et al.
    Used to upgrade the CL algorithm to CLP; the paper cites CLMP25 without proving the equality.
  • standard math Exchange graph path and cycle lemmas of Schrijver, including Theorem 5.1 and Lemma 5.3.
    Used to relate minimum-weight paths and cycles in the exchange graph to minimum-weight common independent sets of size k+1 and to toggled size-k sets.
  • domain assumption The Agarwala-Mertz algorithm can produce a minimum-weight perfect matching in CLP.
    Lemma 2.17 reduces minimum-weight minimum-hop cycle to minimum-weight perfect matching and calls Agarwala-Mertz as a black box; this weighted capability is not stated in this paper's description of that result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear Matroid Intersection is in Catalytic Logspace." pith.science (2026). https://pith.science/paper/XJUHCUNB

@misc{pith2026250906435,
  author       = {Pith},
  title        = {Pith review of: Linear Matroid Intersection is in Catalytic Logspace},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XJUHCUNB}},
  note         = {Machine review of arXiv:2509.06435}
}
abstract

Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to \textit{catalytic space}, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of $\mathsf{P}$. We address this problem for the class catalytic logspace ($\mathsf{CL}$) with a polynomial time bound ($\mathsf{CLP}$). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class $\mathsf{CLP}\subseteq \mathsf{P}$. This was the first subclass of $\mathsf{P}$ shown to contain bipartite matching, and additionally the first problem outside $\mathsf{TC}^1$ shown to be contained in $\mathsf{CL}$. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in $\mathsf{CLP}$.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 42 canonical work pages

  1. [1]

    The complexity of matrix rank and feasible systems of linear equations (extended abstract)

    Eric Allender, Robert Beals, and Mitsunori Ogihara. The complexity of matrix rank and feasible systems of linear equations (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , STOC '96, page 161–167, New York, NY, USA, 1996. Association for Computing Machinery. https://doi.org/10.1145/237814.237856 doi:10....

    work page arXiv 1996

  2. [2]

    Martin Aigner and Thomas A. Dowling. Matching theory for combinatorial geometries. Transactions of the American Mathematical Society , 158:231--245, 1971. https://doi.org/10.1090/S0002-9947-1971-0286689-5 doi:10.1090/S0002-9947-1971-0286689-5

    work page doi:10.1090/s0002-9947-1971-0286689-5 1971

  3. [3]

    Catalytic Computing and Register Programs Beyond Log-Depth

    Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, and Antoine Vinciguerra. Catalytic computing and register programs beyond log- depth. arXiv preprint arXiv:2504.17412 , 2025

    work page Pith review arXiv 2025

  4. [4]

    Impossibility of derandomizing the isolation lemma for all families

    Manindra Agrawal, Rohit Gurjar, and Thomas Thierauf. Impossibility of derandomizing the isolation lemma for all families. In Electron. Colloquium Comput. Complex , volume 27, page 98, 2020

    work page 2020

  5. [5]

    Derandomizing the isolation lemma and lower bounds for circuit size

    Vikraman Arvind and Partha Mukhopadhyay. Derandomizing the isolation lemma and lower bounds for circuit size. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques: 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings , pages 276--289. S...

    work page 2008

  6. [6]

    Bipartite matching is in catalytic logspace

    Aryan Agarwala and Ian Mertz. Bipartite matching is in catalytic logspace. In IEEE Symposium on Foundations of Computer Science (FOCS) , 2025

    work page 2025

  7. [7]

    Matching is as Easy as the Decision Problem, in the NC Model

    Nima Anari and Vijay V Vazirani. Matching is as easy as the decision problem, in the nc model. arXiv preprint arXiv:1901.10387 , 2019

    work page Pith review arXiv 1901

  8. [8]

    Computing with a full memory: catalytic space

    Harry Buhrman, Richard Cleve, Michal Kouck \' y , Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In ACM Symposium on Theory of Computing (STOC) , pages 857--866, 2014. https://doi.org/10.1145/2591796.2591874 doi:10.1145/2591796.2591874

    arXiv 2014

Show all 59 references
  1. [9]

    Almost-catalytic computation

    Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, and Jayalal Sarma. Almost-catalytic computation. Electronic Colloquium on Computational Complexity (ECCC) , TR24-140 , 2024. URL: https://eccc.weizmann.ac.il/report/2024/140

    2024

  2. [10]

    On pure space vs catalytic space

    Sagar Bisoyi, Krishnamoorthy Dinesh, and Jayalal Sarma. On pure space vs catalytic space. Theoretical Computer Science (TCS) , 921:112--126, 2022. https://doi.org/10.1016/J.TCS.2022.04.005 doi:10.1016/J.TCS.2022.04.005

    2022 doi

  3. [11]

    Two theorems in graph theory

    Claude Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences , 43(9):842--844, 1957. https://doi.org/10.1073/pnas.43.9.842 doi:10.1073/pnas.43.9.842

    1957 doi

  4. [12]

    Quantum catalytic space

    Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, and Quinten Tupker. Quantum catalytic space. arXiv preprint arXiv:2506.16324 , 2025

    2025 arXiv

  5. [13]

    Catalytic space: Non-determinism and hierarchy

    Harry Buhrman, Michal Kouck \' y , Bruno Loff, and Florian Speelman. Catalytic space: Non-determinism and hierarchy. Theory of Computing Systems (TOCS) , 62(1):116--135, 2018. https://doi.org/10.1007/S00224-017-9784-7 doi:10.1007/S00224-017-9784-7

    2018 doi

  6. [14]

    Comments on bases in dependence structures

    Richard A Brualdi. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society , 1(2):161--167, 1969

    1969

  7. [15]

    Directed planar reachability is in unambiguous log-space

    Chris Bourke, Raghunath Tewari, and NV Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory (TOCT) , 1(1):1--17, 2009

    2009

  8. [16]

    The structure of catalytic space: Capturing randomness and time via compression

    James Cook, Jiatu Li, Ian Mertz, and Edward Pyne. The structure of catalytic space: Capturing randomness and time via compression. In ACM Symposium on Theory of Computing (STOC) , 2025

    2025

  9. [17]

    Catalytic approaches to the tree evaluation problem

    James Cook and Ian Mertz. Catalytic approaches to the tree evaluation problem. In ACM Symposium on Theory of Computing (STOC) , pages 752--760. ACM , 2020. https://doi.org/10.1145/3357713.3384316 doi:10.1145/3357713.3384316

    2020

  10. [18]

    Encodings and the tree evaluation problem

    James Cook and Ian Mertz. Encodings and the tree evaluation problem. Electronic Colloquium on Computational Complexity (ECCC) , TR21-054 , 2021. URL: https://eccc.weizmann.ac.il/report/2021/054

    2021

  11. [19]

    Trading time and space in catalytic branching programs

    James Cook and Ian Mertz. Trading time and space in catalytic branching programs. In IEEE Conference on Computational Complexity (CCC) , volume 234 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 8:1--8:21, 2022. https://doi.org/10.4230/LIPIcs.CCC.2022.8 d...

    2022 doi

  12. [20]

    Tree evaluation is in space O (log n \( \) log log n)

    James Cook and Ian Mertz. Tree evaluation is in space O (log n \( \) log log n). In ACM Symposium on Theory of Computing (STOC) , pages 1268--1278. ACM , 2024. https://doi.org/10.1145/3618260.3649664 doi:10.1145/3618260.3649664

    2024

  13. [21]

    Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam

    Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam. Pebbles and branching programs for tree evaluation. ACM Transactions on Computational Theory (TOCT) , 3(2):4:1--4:43, 2012. https://doi.org/10.1145/2077336.2077337 doi:10.1145/2077336.2077337

    2012

  14. [22]

    Randomness-optimal unique element isolation, with applications to perfect matching and related problems

    Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Randomness-optimal unique element isolation, with applications to perfect matching and related problems. In Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing , pages 458--467, 1993

    1993

  15. [23]

    Randomized and symmetric catalytic computation

    Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Randomized and symmetric catalytic computation. In CSR , volume 12159 of Lecture Notes in Computer Science (LNCS) , pages 211--223. Springer, 2020. https://doi.org/10.1007/978-3-030-50026-9\_15 doi:...

    2020 doi

  16. [24]

    Matroid partition

    Jack Edmonds. Matroid partition. In George B. Dantzig and A. F. Veinott, editors, Mathematics of the Decision Sciences, Part I , volume 11 of Lectures in Applied Mathematics , pages 335--345. American Mathematical Society, Providence, RI, 1968. Proceedings of the Fifth Summer ...

    1968

  17. [25]

    Submodular functions, matroids, and certain polyhedra

    Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Schönheim, editors, Combinatorial Structures and Their Applications , pages 69--87. Gordon and Breach, New York, 1970

    1970

  18. [26]

    Matroid intersection

    Jack Edmonds. Matroid intersection. In P. L. Hammer, E. L. Johnson, and B. H. Korte, editors, Discrete Optimization I , volume 4 of Annals of Discrete Mathematics , pages 39--49. North‐Holland, Amsterdam, 1979

    1979

  19. [27]

    Bipartite perfect matching is in quasi-nc

    Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 754--763, 2016

    2016

  20. [28]

    Fully characterizing lossy catalytic computation

    Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker. Fully characterizing lossy catalytic computation. In Innovations in Theoretical Computer Science Conference (ITCS) , volume 325 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 50:1--50:13, 2025

    2025

  21. [29]

    A primal approach to the independent assignment problem

    Satoru Fujishige. A primal approach to the independent assignment problem. Journal of the Operations Research Society of Japan , 20(1):1--15, 1977

    1977

  22. [30]

    Unambiguous catalytic computation

    Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Unambiguous catalytic computation. In Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , volume 150 of Leibniz International Proceedings in Informatics (LIPIcs) , pages ...

    2019 doi

  23. [31]

    Lossy catalytic computation

    Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Lossy catalytic computation. Computing Research Repository (CoRR) , abs/2408.14670, 2024

    2024 arXiv

  24. [32]

    Linear matroid intersection is in quasi-nc

    Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-nc. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 821--830, 2017

    2017

  25. [33]

    Isolating a vertex via lattices: Polytopes with totally unimodular faces

    Rohit Gurjar, Thomas Thierauf, and Nisheeth K Vishnoi. Isolating a vertex via lattices: Polytopes with totally unimodular faces. SIAM Journal on Computing , 50(2):636--661, 2021

    2021

  26. [34]

    Collapsing catalytic classes

    Michal Kouck\' y , Ian Mertz, Ted Pyne, and Sasha Sami. Collapsing catalytic classes. Electronic Colloquium on Computational Complexity (ECCC) , TR25-018 , 2025. URL: https://eccc.weizmann.ac.il/report/2025/018

    2025

  27. [35]

    Catalytic computation

    Michal Kouck \' y . Catalytic computation. Bulletin of the EATCS (B.EATCS) , 118, 2016

    2016

  28. [36]

    A combinatorial base for some optimal matroid intersection algorithms

    Stein Krogdahl. A combinatorial base for some optimal matroid intersection algorithms. Technical report, Computer Science Department, Stanford University, Stanford, California, 1974

    1974

  29. [37]

    A combinatorial proof for a weighted matroid intersection algorithm

    Stein Krogdahl. A combinatorial proof for a weighted matroid intersection algorithm. Computer Science Report , 17, 1976

    1976

  30. [38]

    The dependence graph for bases in matroids

    Stein Krogdahl. The dependence graph for bases in matroids. Discrete Mathematics , 19(1):47--59, 1977

    1977

  31. [39]

    Randomness efficient identity testing of multivariate polynomials

    Adam R Klivans and Daniel Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the thirty-third annual ACM symposium on Theory of computing , pages 216--223, 2001

    2001

  32. [40]

    Trading determinism for time in space bounded computations

    Vivek Anand T Kallampally and Raghunath Tewari. Trading determinism for time in space bounded computations. arXiv preprint arXiv:1606.04649 , 2016

    2016 arXiv

  33. [41]

    The hungarian method for the assignment problem

    Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly , 2(1-2):83--97, 1955

    1955

  34. [42]

    Eugene L. Lawler. Matroid intersection algorithms. Mathematical Programming , 9(1):31--56, 1975. https://doi.org/10.1007/BF01681329 doi:10.1007/BF01681329

    1975 doi

  35. [43]

    The matroid matching problem

    L \'a szl \'o Lov \'a sz. The matroid matching problem. Algebraic methods in graph theory , 2:495--517, 1978

    1978

  36. [44]

    On determinants, matchings, and random algorithms

    L \'a szl \'o Lov \'a sz. On determinants, matchings, and random algorithms. In FCT , volume 79, pages 565--574, 1979

    1979

  37. [45]

    Matroid matching and some applications

    L \'a szl \'o Lov \'a sz. Matroid matching and some applications. Journal of Combinatorial Theory, Series B , 28(2):208--236, 1980

    1980

  38. [46]

    A fast parallel algorithm for minimum-cost small integral flows

    Andrzej Lingas and Mia Persson. A fast parallel algorithm for minimum-cost small integral flows. Algorithmica , 72:607--619, 2015

    2015

  39. [47]

    Reusing space: Techniques and open problems

    Ian Mertz. Reusing space: Techniques and open problems. Bulletin of the EATCS (B.EATCS) , 141:57--106, 2023

    2023

  40. [48]

    Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chic. J. Theor. Comput. Sci. , 1997, 1997

    1997

  41. [49]

    Matching is as easy as matrix inversion

    Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages 345--354, 1987

    1987

  42. [50]

    Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees

    Hariharan Narayanan, Huzur Saran, and Vijay V Vazirani. Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees. SIAM Journal on Computing , 23(2):387--397, 1994

    1994

  43. [51]

    Parallel algorithms for the assignment and minimum-cost flow problems

    James B Orlin and Clifford Stein. Parallel algorithms for the assignment and minimum-cost flow problems. Operations research letters , 14(4):181--186, 1993

    1993

  44. [52]

    A note on amortized branching program complexity

    Aaron Potechin. A note on amortized branching program complexity. In IEEE Conference on Computational Complexity (CCC) , volume 79 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 4:1--4:12. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2017. http...

    2017 doi

  45. [53]

    Sheffield, and William Wang

    Edward Pyne, Nathan S. Sheffield, and William Wang. Catalytic communication. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA , volume 325 of LIPIcs , pages 79:1--79:24. Sc...

    2025 doi

  46. [54]

    Making nondeterminism unambiguous

    Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM Journal on Computing , 29(4):1118--1131, 2000

    2000

  47. [55]

    Amortized circuit complexity, formal complexity measures, and catalytic algorithms

    Robert Robere and Jeroen Zuiddam. Amortized circuit complexity, formal complexity measures, and catalytic algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS) , pages 759--769. IEEE , 2021. https://doi.org/10.1109/FOCS52979.2021.00079 doi:10.1109/FOCS52979.2...

    2021

  48. [56]

    Combinatorial Optimization: Polyhedra and Efficiency , volume 24 of Algorithms and Combinatorics

    Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency , volume 24 of Algorithms and Combinatorics . Springer Berlin Heidelberg, 2003

    2003

  49. [57]

    Derandomizing isolation in space-bounded settings

    Dieter Van Melkebeek and Gautam Prakriya. Derandomizing isolation in space-bounded settings. SIAM Journal on Computing , 48(3):979--1021, 2019

    2019

  50. [58]

    On the abstract properties of linear dependence

    Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathematics , 57(3):509--533, July 1935. https://doi.org/10.2307/2371182 doi:10.2307/2371182

    1935 doi

  51. [59]

    Simulating time in square-root space

    Ryan Williams. Simulating time in square-root space. In ACM Symposium on Theory of Computing (STOC) , 2025

    2025

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.