Cover Image

Distributed Sparsest Cut via Eigenvalue Estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Maus, Yannic, de Vos, Tijn
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Distributed Santa Claus via Global Rounding
by: de Vos, Tijn, et al.
Published: (2026)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
by: Chekuri, Chandra, et al.
Published: (2024)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

On Distributed Colouring of Hyperbolic Random Graphs
by: Maus, Yannic, et al.
Published: (2025)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
by: Cruciani, Emilio, et al.
Published: (2025)

Towards Optimal Distributed Delta Coloring
by: Jakob, Manuel, et al.
Published: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

Distributed Delta-Coloring under Bandwidth Limitations
by: Maus, Yannic, et al.
Published: (2024)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
by: Baguley, Samuel, et al.
Published: (2024)

Fast Deterministic Distributed Degree Splitting
by: Maus, Yannic, et al.
Published: (2026)

Towards Optimal Distributed Edge Coloring with Fewer Colors
by: Jakob, Manuel, et al.
Published: (2025)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

Distributed Lovász Local Lemma under Bandwidth Limitations
by: Halldórsson, Magnús M., et al.
Published: (2024)

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
by: Flin, Maxime, et al.
Published: (2026)

Adaptive Massively Parallel Coloring in Sparse Graphs
by: Latypov, Rustam, et al.
Published: (2024)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
by: Cheng, Yu, et al.
Published: (2024)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
by: d'Orsi, Tommaso, et al.
Published: (2024)

On the Locality of Hall's Theorem
by: Brandt, Sebastian, et al.
Published: (2025)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
by: Bakshi, Ainesh, et al.
Published: (2026)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Maximizing the Minimum Eigenvalue in Constant Dimension
by: Brown, Adam, et al.
Published: (2024)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
by: Buchbinder, Niv, et al.
Published: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Sketching Cuts in Graphs and Hypergraphs
by: Kogan, Dmitry, et al.
Published: (2014)

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Online Distributed Queue Length Estimation
by: Bhaskara, Aditya, et al.
Published: (2025)

Distribution Testing Meets Sum Estimation
by: Pradhan, Pinki, et al.
Published: (2025)

Faster Global Minimum Cut with Predictions
by: Moseley, Benjamin, et al.
Published: (2025)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Cut-Query Algorithms with Few Rounds
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)