Worst-Case to Expander-Case Reductions
summary
Shows that many graph problems reduce to expander instances by a simple gadget: add an expansion layer U of about n vertices and randomly connect original vertices so the resulting graph has conductance constant (if every original degree ≥ 100 log n), then tweak to preserve solution value. Maximum cardinality matching and triangle detection admit direct worst-case to expander-case reductions with near-linear blowup; four-cycle requires edge subdivision (blowup ≈ m) or an expander-decomposition to n^(-ε)-expanders, giving only a partial reduction.
AI-written summary · about
chapters (13)
- 0:00Motivation: The Expander Decomposition Method
- 0:37Expander Graphs
- 1:36Expander Decompositions
- 6:31Maximum Matching and Triangle Detection
- 8:09Basic Expander Construction
- 10:15Reduction for Maximum Cardinality Matching
- 11:52Reduction for Triangle Detection
- 13:53The 4-Cycle Detection Problem
- 14:48Reduction for 4-Cycle Detection
- 16:31Expander Decomposition Based Reductions
- 17:16Expander Decomposition Based Reduction for 4-Cycle
- 19:19Exponential Time Problems
- 21:21Open Questions
related talks
01h 02mFine-Grained Counting Complexity II
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
27mOn the Subexponential Time Complexity of the CSP
26mLower Bounds on the Running Time for Scheduling and Packing Problems
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
01h 02mFine-Grained Counting Complexity I
29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
38mLower Bounds on the Space Complexity of Dynamic Programming