Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Khanna, Sanjeev, Putterman, Aaron, Song, Junkai
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
by: Chen, Shengminjie, et al.
Published: (2026)

Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
by: Jia, He, et al.
Published: (2020)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
by: Khanna, Sanjeev, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
by: Stoian, Mihail
Published: (2024)

Fractional Linear Matroid Matching is in quasi-NC
by: Gurjar, Rohit, et al.
Published: (2024)

Hardness and Algorithmic Results for Roman \{3\}-Domination
by: Reddy, Sangam Balchandar
Published: (2025)

TwinArray Sort: An Ultrarapid Conditional Non-Comparison Based Sorting Algorithm
by: Amini, Amin
Published: (2024)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
by: Rao, Satish
Published: (2025)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Improved Algorithm for Permutation Testing
by: Zhang, Xiaojin
Published: (2020)

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
by: Clinch, Katie, et al.
Published: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)