Worst-case to expander-case reductions: derandomized and generalized

DOI10.4230/LIPICS.ESA.2024.4MaRDI QIDQ7253054zbMATH OpenFDO

Authors Amir Abboud, Nathan Wallheimer

Publication date 26 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2024.4

zbMATH Keywords

\(k\)-clique detectiondensest subgraphdynamic algorithmsexact and parameterized complexityexpander decompositionexpander graphsfine-grained complexitymax-cutmaximum matchingself-reductionsworst-case to expander-case

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
• A new approach to estimating effective resistances and counting spanning trees in expander graphs
• A simple deterministic algorithm for edge connectivity
• Deterministic 3SUM-hardness
• Deterministic Edge Connectivity in Near-Linear Time
• Deterministic min-cut in poly-logarithmic max-flows
• Deterministic mincut in almost-linear time
• Deterministic near-linear time minimum cut in weighted graphs
• Distance Oracles for Sparse Graphs
• Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
• Dynamic minimum spanning forest with subpolynomial worst-case update time
• Expander decomposition and pruning: faster, stronger, and simpler
• Expander decomposition in dynamic streams
• Fine-grained complexity lower bounds for families of dynamic graphs
• Graph Clustering using Effective Resistance
• scientific article; zbMATH DE number 5485558 (Why is no real title available?)
• scientific article; zbMATH DE number 7788470 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Max CUT and the smallest eigenvalue
• Maximum flow and minimum-cost flow in almost-linear time
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On clusterings: good, bad and spectral
• Reducing \textsf{3SUM} to \textsf{Convolution-3SUM}
• Subcubic algorithms for Gomory–Hu tree in unweighted graphs
• Sublinear-time algorithms for \textsc{Max Cut, Max E2Lin}\((q)\), and unique label cover on expanders
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Worst-case to expander-case reductions

This page was built for publication: Worst-case to expander-case reductions: derandomized and generalized

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253054)