A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
summary
Introduces a dual cut-toggling algorithm for solving Lx = b that mirrors KOSZ: it maintains vertex potentials on a low-stretch spanning tree, samples fundamental cuts, and adds the exact constant to satisfy flow conservation. Claim: it needs Õ(m) iterations but naive updates cost O(n) each, yielding Õ(mn). Under the OMv lower bound per-iteration o(n) is unlikely if done sequentially. By batching (contracting unaffected tree edges, best at batch size √n) runtime improves to Õ(m1.5) and with sparsification/recursion to Õ(m1+o(1)).
AI-written summary · about
chapters (15)
- 0:00Introduction
- 0:18The Problem
- 1:07Why Care
- 1:22Previous Work
- 4:24Optimality Conditions
- 7:17Detailed Example
- 9:11CutToggling
- 10:01Research Question
- 10:27Discussion
- 12:05KPT Conditions
- 12:45Dual Codes
- 14:00Sample Cuts
- 15:54Batching
- 17:45Not in this talk
- 18:44Summary
related talks
29mSpotting Trees with Few Leaves
31mConstructive Algorithm for Matroid Pathwidth
49mGraph Based Processing of Big Images
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
38mLower Bounds on the Space Complexity of Dynamic Programming
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams