Copertina

On the Streaming Complexity of Expander Decomposition

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chen, Yu, Kapralov, Michael, Makarov, Mikhail, Mazzali, Davide
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
di: Kapralov, Michael, et al.
Pubblicazione: (2024)

Spectral Clustering with Side Information
di: Fichtenberger, Hendrik, et al.
Pubblicazione: (2025)

Streaming Algorithms for Connectivity Augmentation
di: Jin, Ce, et al.
Pubblicazione: (2024)

Improved Directed Expander Decompositions
di: Fleischmann, Henry, et al.
Pubblicazione: (2025)

Expander Decomposition with Almost Optimal Overhead
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Simple Length-Constrained Expander Decompositions
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
di: Sulser, Aurelio L., et al.
Pubblicazione: (2024)

Expander Decomposition for Non-Uniform Vertex Measures
di: Agassy, Daniel, et al.
Pubblicazione: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
di: Chen, Daoyuan, et al.
Pubblicazione: (2024)

New Structures and Algorithms for Length-Constrained Expander Decompositions
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Faster Weak Expander Decompositions and Approximate Max Flow
di: Fleischmann, Henry, et al.
Pubblicazione: (2025)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
di: Charikar, Moses, et al.
Pubblicazione: (2024)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
di: Gutenberg, Maximilian Probst, et al.
Pubblicazione: (2025)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
di: Agassy, Daniel, et al.
Pubblicazione: (2022)

Spectral Clustering in Birthday Paradox Time
di: Kapralov, Michael, et al.
Pubblicazione: (2026)

Recovering Communities in Structured Random Graphs
di: Kapralov, Michael, et al.
Pubblicazione: (2026)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
di: Anand, Aditya, et al.
Pubblicazione: (2025)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
di: Aamand, Anders, et al.
Pubblicazione: (2025)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
di: Jiang, Shunhua, et al.
Pubblicazione: (2025)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
di: Bhaskara, Aditya, et al.
Pubblicazione: (2024)

Expanderizing Higher Order Random Walks
di: Alev, Vedat Levi, et al.
Pubblicazione: (2024)

Optimal Electrical Oblivious Routing on Expanders
di: Florescu, Cella, et al.
Pubblicazione: (2024)

Finding Colorings in One-Sided Expanders
di: Buhai, Rares-Darius, et al.
Pubblicazione: (2025)

Streaming Attention Approximation via Discrepancy Theory
di: Kochetkova, Ekaterina, et al.
Pubblicazione: (2025)

Sublinear Time Low-Rank Approximation of Hankel Matrices
di: Kapralov, Michael, et al.
Pubblicazione: (2025)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
di: Kapralov, Michael, et al.
Pubblicazione: (2022)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
di: Abboud, Amir, et al.
Pubblicazione: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
di: Peng, Pan, et al.
Pubblicazione: (2026)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
di: Long, Yaowei, et al.
Pubblicazione: (2024)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
di: Indyk, Piotr, et al.
Pubblicazione: (2025)

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

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

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
di: Bucić, Matija, et al.
Pubblicazione: (2025)

Sketching and Streaming for Dictionary Compression
di: Becker, Ruben, et al.
Pubblicazione: (2023)

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2022)

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

Expander Hierarchies for Normalized Cuts on Graphs
di: Hanauer, Kathrin, et al.
Pubblicazione: (2024)

GraphBLAS Mathematical Opportunities: Parallel Hypersparse, Matrix Based Graph Streaming, and Complex-Index Matrices
di: Jananthan, Hayden, et al.
Pubblicazione: (2025)