Copertina

Optimal Parallel Basis Finding in Graphic and Related Matroids

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Khanna, Sanjeev, Putterman, Aaron, Song, Junkai
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
di: Dhar, Anubhav, et al.
Pubblicazione: (2025)

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

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

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

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

The Complexity of Finding and Counting Subtournaments
di: Döring, Simon, et al.
Pubblicazione: (2025)

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

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Finding Maximum Common Contractions Between Phylogenetic Networks
di: Marchand, Bertrand, et al.
Pubblicazione: (2024)

Finding One Local Optimum Is Easy -- but What About Two?
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2025)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
di: Shih, Yu-Sheng, et al.
Pubblicazione: (2026)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
di: de Berg, Mark, et al.
Pubblicazione: (2025)

Linear Hashing Is Optimal
di: Jaber, Michael, et al.
Pubblicazione: (2025)

On Optimal Testing of Linearity
di: Arora, Vipul, et al.
Pubblicazione: (2024)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
di: Dey, Palash, et al.
Pubblicazione: (2026)

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

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
di: Tani, Seiichiro
Pubblicazione: (2019)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
di: Grüttemeier, Niels, et al.
Pubblicazione: (2025)

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

Near-Optimal Averaging Samplers and Matrix Samplers
di: Xun, Zhiyang, et al.
Pubblicazione: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
di: Minzer, Dor, et al.
Pubblicazione: (2024)

Cluster Editing on Cographs and Related Classes
di: Lafond, Manuel, et al.
Pubblicazione: (2024)

Near-Optimality for Single-Source Personalized PageRank
di: Jiang, Xinpeng, et al.
Pubblicazione: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
di: Singer, Noah G., et al.
Pubblicazione: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
di: Wallisch, Christian, et al.
Pubblicazione: (2025)

MAX BISECTION might be harder to approximate than MAX CUT
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

On the Mysteries of MAX NAE-SAT
di: Brakensiek, Joshua, et al.
Pubblicazione: (2020)