arxiv: 2605.03979 · v1 · submitted 2026-05-05 · 💻 cs.DS · cs.CC

Recognition: unknown

An widetilde{O} (n^{3/7}) Round Parallel Algorithm for Matroid Bases

Aaron Putterman, Junkai Song, Sanjeev Khanna

Authors on Pith no claims yet

Pith reviewed 2026-05-07 13:35 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords matroid basisparallel algorithmsindependence oracleadaptive complexityrandom circuitscombinatorial optimizationquery complexity

0 comments

The pith

A new parallel algorithm finds a matroid basis in roughly n to the 3/7 adaptive rounds.

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

The paper gives an algorithm that finds a basis for any n-element matroid using an independence oracle in tilde O of n to the 3/7 rounds. This improves the best previous upper bound of tilde O of n to the 7/15 and narrows the long-standing gap with the known lower bound of roughly n to the 1/3. The advance comes from a new way to analyze random circuits that tracks how linear dependencies can involve several elements at once instead of one element at a time. If the bound holds, it shows that many matroid problems admit substantially more parallel speed-up than was previously known.

Core claim

The authors present a structural and algorithmic framework that finds a matroid basis in tilde O of n to the 3/7 rounds. The framework replaces element-by-element reasoning about random circuits with simultaneous analysis of multi-element dependencies, allowing the algorithm to certify progress across batches of queries in each round.

What carries the argument

A structural framework for random circuits that reasons simultaneously about multi-element linear dependencies.

If this is right

The upper bound on adaptive rounds for finding a matroid basis drops from n to the 7/15 to n to the 3/7.
The gap between upper and lower bounds on the parallel complexity narrows from n to the 7/15 versus n to the 1/3 toward n to the 3/7 versus n to the 1/3.
The same multi-element dependency analysis can be reused to accelerate other oracle-based matroid algorithms that rely on random circuit sampling.
Partition matroids and other simple matroids inherit the same improved round bound as a direct corollary.

Where Pith is reading between the lines

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

Refining the multi-element circuit analysis might push the upper bound closer to the n to the 1/3 lower bound without new lower-bound techniques.
The framework could extend to matroid intersection or other multi-matroid problems where dependencies across structures must be tracked in parallel.
If the same lens applies to non-linear dependence oracles, similar round reductions may appear in related combinatorial search problems.

Load-bearing premise

The analysis depends on a new structural framework for random circuits that lets the algorithm reason about multi-element dependencies simultaneously.

What would settle it

An explicit matroid on n elements together with an execution trace showing that the algorithm needs more than n to the 3/7 rounds on that instance.

read the original abstract

We study the parallel (adaptive) complexity of the classic problem of finding a basis in an $n$-element matroid, given access via an \emph{independence oracle}. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS~1985, JCSS~1988; hereafter KUW) initiated this study, showing that $O(\sqrt{n})$ adaptive rounds suffice for any matroid, and that $\widetilde\Omega(n^{1/3})$ rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS~2025; hereafter KPS) achieved $\widetilde O(n^{7/15})$ rounds, the first improvement since~KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in $\widetilde O(n^{3/7})$ rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously.

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 improves matroid basis finding to Õ(n^{3/7}) rounds via a multi-element view of random circuits, a modest but clean step past the 2025 KPS bound.

read the letter

This paper gives a new parallel algorithm that finds a basis in any n-element matroid using Õ(n^{3/7}) adaptive rounds with an independence oracle. That beats the Õ(n^{7/15}) bound from Khanna-Putterman-Song last year and narrows the long-standing gap to the Õ(n^{1/3}) lower bound that has held since Karp-Upfal-Wigderson in 1985. The core advance is a structural framework that tracks dependencies across multiple elements in random circuits at once, rather than element by element. This produces a better recurrence whose solution yields the improved exponent. The abstract and the internal consistency check on the key lemmas both line up without obvious circularity or oracle assumptions that would break the argument. The positioning against prior work is straightforward and gives proper credit. The improvement itself is incremental—3/7 is roughly 0.428 versus 0.466—but it is a genuine advance in the exponent and comes from a fresh way of looking at the circuits. The analysis is likely technical and will need careful referee scrutiny, but nothing in the provided material flags a load-bearing gap. This is for readers who follow parallel algorithms, adaptive complexity, and matroid problems. Someone working in those areas will get value from the new lens on circuits even if they do not adopt the exact bound. I would bring the paper to a reading group to walk through the recurrence and the multi-element lemmas. It deserves serious peer review because the result is new, the approach is honest, and the claimed improvement is internally consistent.

Referee Report

0 major / 3 minor

Summary. The paper presents a new adaptive parallel algorithm for finding a basis in an n-element matroid given access to an independence oracle. It achieves an improved round complexity of Õ(n^{3/7}), improving on the prior Õ(n^{7/15}) bound of Khanna, Putterman, and Song (FOCS 2025). The central technical contribution is a structural and algorithmic framework for analyzing random circuits that reasons simultaneously about multi-element dependencies rather than individual elements, yielding a new recurrence whose solution gives the claimed bound.

Significance. If the analysis holds, the result narrows the long-standing gap between the KUW upper bound of O(√n) and the Õ(n^{1/3}) lower bound for partition matroids, representing the first improvement since KPS. The new lens on random-circuit analysis is a conceptual advance that may apply to other parallel matroid and independence-oracle problems. The manuscript supplies internally consistent lemmas on circuit probabilities and the resulting recurrence, with no evident hidden assumptions on oracle responses or random choices.

minor comments (3)

[§1] §1 (Introduction): the recurrence relation whose solution yields the n^{3/7} exponent is stated at a high level; adding an explicit display of the recurrence (with the parameters tracking multi-element dependencies) would improve readability.
The citation to KPS (FOCS 2025) appears in the abstract but should be cross-checked against the bibliography for completeness and consistency with the full reference list.
[Preliminaries] Notation for the tilde-O notation and the precise dependence on the independence-oracle model could be clarified in the preliminaries to avoid ambiguity for readers unfamiliar with the KUW model.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work, the recognition of its significance as the first improvement since KPS, and the recommendation for minor revision. The description of our structural framework for multi-element dependencies in random circuits is accurate.

Circularity Check

0 steps flagged

Minor self-citation of prior work by same authors, not load-bearing for new result

full rationale

The manuscript cites the authors' own prior KPS (FOCS 2025) result solely to establish the historical baseline of Õ(n^{7/15}) rounds before presenting the new Õ(n^{3/7}) algorithm. The central contribution is described as a fresh structural framework for analyzing random circuits that tracks multi-element dependencies, yielding an improved recurrence solved directly by the algorithm. No equations, fitted parameters, self-definitional reductions, or load-bearing self-citations appear in the abstract or described derivation; the new bound is presented as an independent algorithmic advance rather than a renaming or fit of prior quantities. This qualifies as at most a minor self-citation that does not reduce the claimed result to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are stated or derivable from the given text.

pith-pipeline@v0.9.0 · 5545 in / 934 out tokens · 22769 ms · 2026-05-07T13:35:12.895439+00:00 · methodology

Review history (3 revisions) →

discussion (0)

Reference graph

Works this paper leans on

155 extracted references · 113 canonical work pages

[1]

Karger , editor =

David R. Karger , editor =. Using Randomized Sparsification to Approximate Minimum Cuts , booktitle =. 1994 , url =

1994
[2]

2010 IEEE 25th Annual Conference on Computational Complexity , pages=

Lower bounds for testing function isomorphism , author=. 2010 IEEE 25th Annual Conference on Computational Complexity , pages=. 2010 , organization=

2010
[3]

Theory of evolutionary computation: Recent developments in discrete optimization , pages=

Probabilistic tools for the analysis of randomized optimization heuristics , author=. Theory of evolutionary computation: Recent developments in discrete optimization , pages=. 2020 , publisher=

2020
[4]

Theoretical Computer Science , volume=

Improved time complexity analysis of the simple genetic algorithm , author=. Theoretical Computer Science , volume=. 2015 , publisher=

2015
[5]

Statistics & Probability Letters , volume=

Binomial approximation to the Poisson binomial distribution , author=. Statistics & Probability Letters , volume=. 1991 , publisher=

1991
[6]

Ashok Subramanian , title =. Inf. Process. Lett. , volume =. 1995 , url =. doi:10.1016/0020-0190(94)00202-A , timestamp =

work page doi:10.1016/0020-0190(94)00202-a 1995
[7]

On determinants, matchings, and random algorithms , booktitle =

L. On determinants, matchings, and random algorithms , booktitle =. 1979 , timestamp =

1979
[8]

Constructing a perfect matching is in random NC

Richard M. Karp and Eli Upfal and Avi Wigderson , title =. Comb. , volume =. 1986 , url =. doi:10.1007/BF02579407 , timestamp =

work page doi:10.1007/bf02579407 1986
[9]

Karp and Eli Upfal and Avi Wigderson , title =

Richard M. Karp and Eli Upfal and Avi Wigderson , title =. J. Comput. Syst. Sci. , volume =. 1988 , url =. doi:10.1016/0022-0000(88)90027-X , timestamp =

work page doi:10.1016/0022-0000(88)90027-x 1988
[10]

2017 , volume =

Ola Svensson and Jakub Tarnawski , editor =. The Matching Problem in General Graphs Is in Quasi-NC , booktitle =. 2017 , url =. doi:10.1109/FOCS.2017.70 , timestamp =

work page doi:10.1109/focs.2017.70 2017
[11]

1986 , url =

Michael Luby , title =. 1986 , url =. doi:10.1137/0215074 , timestamp =

work page doi:10.1137/0215074 1986
[12]

A lower bound for parallel submodular minimization , booktitle =

Eric Balkanski and Yaron Singer , editor =. A lower bound for parallel submodular minimization , booktitle =. 2020 , url =. doi:10.1145/3357713.3384287 , timestamp =

work page doi:10.1145/3357713.3384287 2020
[13]

Deeparnab Chakrabarty and Yu Chen and Sanjeev Khanna , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00013 , timestamp =

work page doi:10.1109/focs52979.2021.00013 2021
[14]

arXiv preprint arXiv:2511.04826 , year=

Optimal Parallel Basis Finding in Graphic and Related Matroids , author=. arXiv preprint arXiv:2511.04826 , year=

work page arXiv
[15]

A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision , booktitle =

Sumanta Ghosh and Rohit Gurjar and Roshan Raj , editor =. A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision , booktitle =. 2022 , url =. doi:10.1137/1.9781611977073.44 , timestamp =

work page doi:10.1137/1.9781611977073.44 2022
[16]

Combinatorica , volume=

On the number of matroids , author=. Combinatorica , volume=. 2015 , publisher=

2015
[17]

Mohsen Ghaffari and Christoph Grunau , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00007 , timestamp =

work page doi:10.1109/focs61266.2024.00007 2024
[18]

Vishnoi , editor =

Rohit Gurjar and Nisheeth K. Vishnoi , editor =. On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes) , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.53 , timestamp =

work page doi:10.1137/1.9781611975482.53 2019
[19]

Deeparnab Chakrabarty and Andrei Graur and Haotian Jiang and Aaron Sidford , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00030 , timestamp =

work page doi:10.1109/focs54457.2022.00030 2022
[20]

Karger , editor =

David R. Karger , editor =. Random sampling in cut, flow, and network design problems , booktitle =. 1994 , url =. doi:10.1145/195058.195422 , timestamp =

work page doi:10.1145/195058.195422 1994
[21]

Benson and Jon M

Nate Veldt and Austin R. Benson and Jon M. Kleinberg , title =. 2022 , url =. doi:10.1137/20M1321048 , timestamp =

work page doi:10.1137/20m1321048 2022
[22]

CoRR , volume =

Venkatesan Guruswami and Jonathan Mosheiff , title =. CoRR , volume =. 2021 , url =. 2109.11725 , timestamp =

work page arXiv 2021
[23]

Annals of Mathematics , year =

Omer Reingold and Salil Vadhan and Avi Wigderson , title =. Annals of Mathematics , year =
[24]

Bulletin of the American Mathematical Society , year=

Expander Graphs and their Applications , author=. Bulletin of the American Mathematical Society , year=
[25]

Three XOR-Lemmas - An Exposition , booktitle =

Oded Goldreich , editor =. Three XOR-Lemmas - An Exposition , booktitle =. 2011 , url =. doi:10.1007/978-3-642-22670-0\_22 , timestamp =

work page doi:10.1007/978-3-642-22670-0 2011
[26]

Problemy Peredachi Informatsii , volume=

List concatenated decoding , author=. Problemy Peredachi Informatsii , volume=. 1981 , publisher=

1981
[27]

It'll Probably Work Out: Improved List-Decoding Through Random Operations , booktitle =

Atri Rudra and Mary Wootters , editor =. It'll Probably Work Out: Improved List-Decoding Through Random Operations , booktitle =. 2015 , url =. doi:10.1145/2688073.2688092 , timestamp =

work page doi:10.1145/2688073.2688092 2015
[28]

On the List Recoverability of Randomly Punctured Codes , booktitle =

Ben Lund and Aditya Potukuchi , editor =. On the List Recoverability of Randomly Punctured Codes , booktitle =. 2020 , url =. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.30 , timestamp =

work page doi:10.4230/lipics.approx/random.2020.30 2020
[29]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages =

Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro , title =. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2020 , isbn =. doi:10.1145/3357713.3384231 , abstract =

work page doi:10.1145/3357713.3384231 2020
[30]

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

Ta-Shma, Amnon , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2017 , isbn =. doi:10.1145/3055399.3055408 , abstract =

work page doi:10.1145/3055399.3055408 2017
[31]

List-Decodability With Large Radius for Reed-Solomon Codes , year=

Ferber, Asaf and Kwan, Matthew and Sauermann, Lisa , journal=. List-Decodability With Large Radius for Reed-Solomon Codes , year=
[32]

Hardness vs randomness , journal =

Noam Nisan and Avi Wigderson , abstract =. Hardness vs randomness , journal =. 1994 , issn =. doi:https://doi.org/10.1016/S0022-0000(05)80043-1 , url =

work page doi:10.1016/s0022-0000(05)80043-1 1994
[33]

doi:10.1016/0010-4655(94)90232-1 , url =

Martin Lüscher , title =. doi:10.1016/0010-4655(94)90232-1 , url =

work page doi:10.1016/0010-4655(94)90232-1
[34]

Jonathan Mosheiff and Nicolas Resch and Noga Ron. 61st. 2020 , url =. doi:10.1109/FOCS46700.2020.00050 , timestamp =

work page doi:10.1109/focs46700.2020.00050 2020
[35]

and Panigrahi, Debmalya , title =

Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993647 , abstract =

work page doi:10.1145/1993636.1993647 2011
[36]

Entanglement is necessary for optimal quantum property testing

Yu Chen and Sanjeev Khanna and Ansh Nagda , editor =. Near-linear Size Hypergraph Cut Sparsifiers , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00015 , timestamp =

work page doi:10.1109/focs46700.2020.00015 2020
[37]

Karger , title =

David R. Karger , title =. Math. Oper. Res. , volume =. 1999 , url =. doi:10.1287/moor.24.2.383 , timestamp =

work page doi:10.1287/moor.24.2.383 1999
[38]

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

Kent Quanrud , title =. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2024 , publisher =. doi:10.1137/1.9781611977912.187 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.187 , abstract =

work page doi:10.1137/1.9781611977912.187 2024
[39]

Approximating

Andr. Approximating. Proceedings of the Twenty-Eighth Annual. 1996 , url =. doi:10.1145/237814.237827 , timestamp =

work page doi:10.1145/237814.237827 1996
[40]

Batson and Daniel A

Joshua D. Batson and Daniel A. Spielman and Nikhil Srivastava , editor =. Twice-. Proceedings of the 41st Annual. 2009 , url =. doi:10.1145/1536414.1536451 , timestamp =

work page doi:10.1145/1536414.1536451 2009
[41]

Liu and Aaron Sidford , editor =

Arun Jambulapati and Yang P. Liu and Aaron Sidford , editor =. Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification , booktitle =. 2023 , url =. doi:10.1145/3564246.3585136 , timestamp =

work page doi:10.1145/3564246.3585136 2023
[42]

Nearly Tight Spectral Sparsification of Directed Hypergraphs , booktitle =

Kazusato Oko and Shinsaku Sakaue and Shin. Nearly Tight Spectral Sparsification of Directed Hypergraphs , booktitle =. 2023 , url =. doi:10.4230/LIPIcs.ICALP.2023.94 , timestamp =

work page doi:10.4230/lipics.icalp.2023.94 2023
[43]

It'll Probably Work Out: Improved List-Decoding Through Random Operations , booktitle =

Dmitry Kogan and Robert Krauthgamer , editor =. Sketching Cuts in Graphs and Hypergraphs , booktitle =. 2015 , url =. doi:10.1145/2688073.2688093 , timestamp =

work page doi:10.1145/2688073.2688093 2015
[44]

2017 , url =

Arnold Filtser and Robert Krauthgamer , title =. 2017 , url =. doi:10.1137/15M1046186 , timestamp =

work page doi:10.1137/15m1046186 2017
[45]

Karger , editor =

David R. Karger , editor =. Global Min-cuts in. Proceedings of the Fourth Annual. 1993 , url =

1993
[46]

Spielman and Shang

Daniel A. Spielman and Shang. Spectral Sparsification of Graphs , journal =. 2011 , url =. doi:10.1137/08074489X , timestamp =

work page doi:10.1137/08074489x 2011
[47]

Lee , editor =

James R. Lee , editor =. Spectral Hypergraph Sparsification via Chaining , booktitle =. 2023 , url =. doi:10.1145/3564246.3585165 , timestamp =

work page doi:10.1145/3564246.3585165 2023
[48]

54th Annual

Jonah Sherman , title =. 54th Annual. 2013 , url =. doi:10.1109/FOCS.2013.36 , timestamp =

work page doi:10.1109/focs.2013.36 2013
[49]

Spielman , editor =

Rasmus Kyng and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Daniel A. Spielman , editor =. Sparsified Cholesky and multigrid solvers for connection laplacians , booktitle =. 2016 , url =. doi:10.1145/2897518.2897640 , timestamp =

work page doi:10.1145/2897518.2897640 2016
[50]

2018 , url =

Yin Tat Lee and He Sun , title =. 2018 , url =. doi:10.1137/16M1061850 , timestamp =

work page doi:10.1137/16m1061850 2018
[51]

Yu Chen and Sanjeev Khanna and Huan Li , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00052 , timestamp =

work page doi:10.1109/focs54457.2022.00052 2022
[52]

Kelner and Yin Tat Lee and Lorenzo Orecchia and Aaron Sidford , editor =

Jonathan A. Kelner and Yin Tat Lee and Lorenzo Orecchia and Aaron Sidford , editor =. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations , booktitle =. 2014 , url =. doi:10.1137/1.9781611973402.16 , timestamp =

work page doi:10.1137/1.9781611973402.16 2014
[53]

Approximate Undirected Maximum Flows in

Richard Peng , editor =. Approximate Undirected Maximum Flows in. Proceedings of the Twenty-Seventh Annual. 2016 , url =. doi:10.1137/1.9781611974331.ch130 , timestamp =

work page doi:10.1137/1.9781611974331.ch130 2016
[54]

Cohen and Rasmus Kyng and Gary L

Michael B. Cohen and Rasmus Kyng and Gary L. Miller and Jakub W. Pachocki and Richard Peng and Anup B. Rao and Shen Chen Xu , editor =. Solving. Symposium on Theory of Computing,. 2014 , url =. doi:10.1145/2591796.2591833 , timestamp =

work page doi:10.1145/2591796.2591833 2014
[55]

CoRR , volume =

Arun Jambulapati and Aaron Sidford , title =. CoRR , volume =. 2020 , url =. 2011.08806 , timestamp =

work page arXiv 2020
[56]

Woodruff and Qin Zhang , editor =

Jiecao Chen and He Sun and David P. Woodruff and Qin Zhang , editor =. Communication-Optimal Distributed Clustering , booktitle =. 2016 , url =

2016
[57]

Spectral Sparsification of Hypergraphs , booktitle =

Tasuku Soma and Yuichi Yoshida , editor =. Spectral Sparsification of Hypergraphs , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.159 , timestamp =

work page doi:10.1137/1.9781611975482.159 2019
[58]

Hastings, and Umesh V

Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , editor =. Towards tight bounds for spectral sparsification of hypergraphs , booktitle =. 2021 , url =. doi:10.1145/3406325.3451061 , timestamp =

work page doi:10.1145/3406325.3451061 2021
[59]

Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00114 , timestamp =

work page doi:10.1109/focs52979.2021.00114 2021
[60]

Patkar , title =

Satoru Fujishige and Sachin B. Patkar , title =. Discret. Math. , volume =. 2001 , url =. doi:10.1016/S0012-365X(00)00164-3 , timestamp =

work page doi:10.1016/s0012-365x(00)00164-3 2001
[61]

Sparsification of Binary

Silvia Butti and Stanislav Zivn. Sparsification of Binary. 2020 , url =. doi:10.1137/19M1242446 , timestamp =

work page doi:10.1137/19m1242446 2020
[62]

CoRR , volume =

Yotam Kenneth and Robert Krauthgamer , title =. CoRR , volume =. 2023 , url =

2023
[63]

Lee and Yang P

Arun Jambulapati and James R. Lee and Yang P. Liu and Aaron Sidford , title =. CoRR , volume =. 2023 , url =. doi:10.48550/arXiv.2305.09049 , eprinttype =. 2305.09049 , timestamp =

work page doi:10.48550/arxiv.2305.09049 2023
[64]

Sparsification of Monotone k-Submodular Functions of Low Curvature , journal =

Jannik Kudla and Stanislav Zivn. Sparsification of Monotone k-Submodular Functions of Low Curvature , journal =. 2023 , url =. doi:10.48550/arXiv.2302.03143 , eprinttype =. 2302.03143 , timestamp =

work page doi:10.48550/arxiv.2302.03143 2023
[65]

Revealing information while preserving privacy , booktitle =

Irit Dinur and Kobbi Nissim , editor =. Revealing information while preserving privacy , booktitle =. 2003 , url =. doi:10.1145/773153.773173 , timestamp =

work page doi:10.1145/773153.773173 2003
[66]

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

Code sparsification and its applications , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

2024
[67]

arXiv preprint arXiv:2402.13151 , year=

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs , author=. arXiv preprint arXiv:2402.13151 , year=

work page arXiv
[68]

Characterizations of Sparsifiability for Affine

Khanna, Sanjeev and Putterman, Aaron L and Sudan, Madhu , journal=. Characterizations of Sparsifiability for Affine
[69]

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers , booktitle=

Khanna, Sanjeev and Putterman, Aaron L and Sudan, Madhu , journal=. Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers , booktitle=
[70]

, keywords =

Pinter, Charles C. , keywords =. 2010 , title =

2010
[71]

Weisstein , title =

Eric W. Weisstein , title =
[72]

Analyzing graph structure via linear measurements , booktitle =

Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Analyzing graph structure via linear measurements , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.40 , timestamp =

work page doi:10.1137/1.9781611973099.40 2012
[73]

Graph sketches: sparsification, spanners, and subgraphs , booktitle =

Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Graph sketches: sparsification, spanners, and subgraphs , booktitle =. 2012 , url =. doi:10.1145/2213556.2213560 , timestamp =

work page doi:10.1145/2213556.2213560 2012
[74]

Vertex and Hyperedge Connectivity in Dynamic Graph Streams , booktitle =

Sudipto Guha and Andrew McGregor and David Tench , editor =. Vertex and Hyperedge Connectivity in Dynamic Graph Streams , booktitle =. 2015 , url =. doi:10.1145/2745754.2745763 , timestamp =

work page doi:10.1145/2745754.2745763 2015
[75]

Woodruff and Mobin Yahyazadeh , editor =

Michael Kapralov and Jelani Nelson and Jakub Pachocki and Zhengyu Wang and David P. Woodruff and Mobin Yahyazadeh , editor =. Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams , booktitle =. 2017 , url =. doi:10.1109/FOCS.2017.50 , timestamp =

work page doi:10.1109/focs.2017.50 2017
[76]

35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994 , pages =

Mihir Bellare and John Rompel , title =. 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994 , pages =. 1994 , url =. doi:10.1109/SFCS.1994.365687 , timestamp =

work page doi:10.1109/sfcs.1994.365687 1994
[77]

Michael Kapralov and Yin Tat Lee and Cameron Musco and Christopher Musco and Aaron Sidford , title =. 55th. 2014 , url =. doi:10.1109/FOCS.2014.66 , timestamp =

work page doi:10.1109/focs.2014.66 2014
[78]

Public vs

Ilan Newman and Mario Szegedy , editor =. Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract) , booktitle =. 1996 , url =. doi:10.1145/237814.238004 , timestamp =

work page doi:10.1145/237814.238004 1996
[79]

CSE 206A: Lattice Algorithms and Applications , pages =

Daniele Miccancio , title =. CSE 206A: Lattice Algorithms and Applications , pages =. 2014 , note =

2014
[80]

Distributed Parallel Databases , volume =

Graham Cormode and Donatella Firmani , title =. Distributed Parallel Databases , volume =. 2014 , url =. doi:10.1007/S10619-013-7131-9 , timestamp =

work page doi:10.1007/s10619-013-7131-9 2014

Showing first 80 references.