Cover Image

Finding Colorings in One-Sided Expanders

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Buhai, Rares-Darius, Hua, Yiding, Steurer, David, Vári-Kakas, Andor
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

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Lasso and Partially-Rotated Designs
by: Buhai, Rares-Darius
Published: (2025)

Robust Mixture Learning when Outliers Overwhelm Small Groups
by: Dmitriev, Daniil, et al.
Published: (2024)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Improved Directed Expander Decompositions
by: Fleischmann, Henry, et al.
Published: (2025)

On the Streaming Complexity of Expander Decomposition
by: Chen, Yu, et al.
Published: (2024)

Multi-View Structural Graph Summaries
by: Frank, Jonatan, et al.
Published: (2024)

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

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

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

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

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

One-Sided Local Crossing Minimization
by: Giannopoulos, Panos, et al.
Published: (2025)

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

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

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

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

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

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

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

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

weberknecht -- a One-Sided Crossing Minimization solver
by: Rauch, Johannes
Published: (2024)

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

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
by: Chen, Hongjie, et al.
Published: (2024)

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

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

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

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

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

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

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

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

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
by: Gharan, Shayan Oveis, et al.
Published: (2025)

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

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

Near-Optimal Bayesian Online Assortment of Reusable Resources
by: Feng, Yiding, et al.
Published: (2025)

Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference
by: Feng, Yiding, et al.
Published: (2026)