Dynamic Graphs and Algorithm Design (Simons Institute, 2023)
2023-09-18..2023-09-22
Berkeley, United States
| title | author | length |
|---|---|---|
| Lightning Talks | 33m | |
Eighteen rapidfire introductions summarize ongoing work and questions across dynamic graph algorithms: lower bounds on expanders, oblivious routing with… | ||
| Approximating Edit Distance in the Fully Dynamic Model | Barna Saha | 50m |
Presents a dynamic algorithm that approximates edit distance with amortized update time n^ε (for any ε>0) at a polylog(n) approximation factor, trading off… | ||
| Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models | Sepideh Mahabadi | 46m |
Survey presents concrete algorithms and bounds: a composable coreset construction achieves composable coreset of size k^{1+ε} with 1/ε approximation for the… | ||
| Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy | Helen Xu | 48m |
Claims a locality-first strategy and builds Terrace, a hierarchical container that colocates low-degree neighbors in a shared PMA + standalone B-tree and uses… | ||
| Parallelism in Dynamic Graph Algorithms | Guy Blelloch | 01h 00m |
Shows concrete parallel algorithms and costs: a batch incremental MST that prunes and compresses the tree with an RC-tree hierarchy and runs in about k… | ||
| Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds | Soheil Behnezhad | 01h 01m |
Recent claims: estimating maximum matching size can run sublinearly and feed fast dynamic algorithms. Concrete results include a greedy oracle that decides… | ||
| A Blackbox Reduction for Adaptive Adversaries using Differential Privacy | Thatchaphol Saranurak | 47m |
A black-box transformation converts any dynamic estimation algorithm that is correct against an oblivious adversary into one robust against an adaptive… | ||
| Dynamic Algorithms for 𝑘-center on Graphs | Sebastian Forster | 51m |
Presents the first algorithms that maintain k-center on an evolving undirected graph by reducing to dynamic (1+ε)-SSSP: a fully dynamic 2+ε approximation with… | ||
| Parallel Batch-Dynamic Graph Representations | Laxman Dhulipala | 53m |
Describes a concrete system called Apsen that extends Ligra and a compressed, block-based purely-functional representation called the CPAM framework; claims… | ||
| Dynamic Matching: Rounding & Sparsification (And New Tools) | David Wajc | 49m |
Shows how to convert dynamic fractional matchings into integral matchings using sparsification via rounding and bulk sampling by edge‑coloring, reducing prior… | ||
| Decremental Shortest Paths against an Adaptive Adversary | Aaron Bernstein | 01h 02m |
Claims a near-optimal deterministic decremental single-source shortest paths data structure that removes the oblivious-adversary assumption and achieves… | ||
| Practical Dynamic Graph Algorithms: Data Structures and Connections Between Models | Quanquan Liu | 43m |
Describes a transferable approach: level data structures that partition vertices into O(log n) levels and move active vertices by checking induced-degree… | ||
| Online List Labeling: Breaking the log^2 n Barrier | Nicole Wein | 49m |
Provides a randomized data structure that stores n items in m = Θ(n) array slots and achieves expected O(log^{3/2} n) item moves per insertion/deletion… | ||
| Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates | Sayan Bhattacharya | 47m |
Maintains fractional solutions to general packing and covering LPs under partially dynamic updates and proves both upper and conditional lower bounds: a… | ||
| Dynamic PageRank: Additive Error and Batch Recomputation | Jakub Lacki | 51m |
Shows a proof that maintaining a constant-factor multiplicative PageRank under n updates is provably hard: any algorithm must take at least n^(1−ε) total time… | ||
| Dynamic Graphs on the GPU | John Owens | 58m |
Claims a practical GPU stack: GPUs have 300,000 threads in flight, ~144 SMs, ~80 GB HBM and ~36 MB L2, and the PCIe/CPU link (~32 GB/s) often bottlenecks real… | ||
| On Engineering Dynamic Graph Algorithms | Kathrin Hanauer | 52m |
Implements two families of dynamic solutions for weighted k-edge-coloring: a randomized dyn-greedy and a modified Misra–Gries-based dyn-kEC, plus a batch… | ||
| On Dynamic Graph Approximations: The case of j-Trees | Gramoz Goranci | 53m |
Proves a dynamic data structure that maintains Madry-style j‑tree approximations so fully dynamic s–t max‑flow queries run with truly sublinear updates: about… | ||
| Minimum Isolating Cuts: A New Tool for Solving Minimum Cut Problems | Jason Li | 41m |
Introduces a concrete procedure called isolating cuts lemma that, given a terminal set containing exactly one vertex from a small side, computes… | ||
| Faster High Accuracy Multi-Commodity Flows via Graph Techniques | Jan van der Brand | 45m |
Graph techniques give a concrète speedup for high‑accuracy multi‑commodity flow by reducing the problem to a dynamic HeavyHitter data structure on incidence… | ||
| Recent Progress on Sublinear Time Algorithms for Maximum Matching: Lower Bounds | Soheil Behnezhad | 47m |
Proves a concrete hardness: any better-than-2/3 approximation to maximum matching in the adjacency‑list model requires about n^{1.2} queries by building a… | ||
| Parallel Batch-Dynamic Graph Algorithms | Julian Shun | 41m |
A parallel batch-dynamic k‑core algorithm maintains 2+ε approximation coreness values with amortized O(B log^2 n) work per batch and polylogarithmic span… | ||
| Accelerating the Multiplicative-Weights Framework for Graph Linear Programs | Omri Weinstein | 53m |
Replaces the standard Min-Inner-Product shortest-path oracle with a packing Min-IP oracle that returns a maximally-disjoint set of short paths (like blocking… | ||
| nothing matches | ||