Fast Algorithms via Spectral Methods 2014
2014-12-01..2014-12-05
Berkeley, United States
[Spectral Algorithms: From Theory to Practice 2014, Sublinear Algorithms and Nearest-Neighbor Search, Dynamic Graphs and Algorithm Design (Simons Institute, 2023), Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Discrete Optimization via Continuous Relaxation, Optimization and Algorithm Design 2023]
as the organisers put it
This workshop aims to bring together researchers interested in the various mathematical and algorithmic tools that underlie dramatic recent developments in fast algorithms for diagonally dominant linear systems and their subsequent application to fast algorithms for combinatorial problems. In particular, this will include researchers from diverse areas of theory including graph sparsification, metric geometry of graphs, data structures and numerical linear algebra. Enquiries may be sent to the organizers at this address.
| title | author | length |
|---|---|---|
| Computing Cut-Based Hierarchical Decompositions in Almost Linear Time | Harald Räcke | 55m |
Constructs a flow sparsifier that is a tree for k-terminal graphs and proves it yields an oblivious routing with similar competitive ratio; quality is roughly… | ||
| An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicom... | Jon Kelner | 01h 09m |
Presents an algorithm that computes a (1 − ε)-approximate max flow in undirected graphs in almost-linear time (m^{1+o(1)}), and extends to multi-commodity… | ||
| Electrical Flows Primitive and Fast Graph Algorithms | Aleksander Madry | 01h 09m |
Argues that electrical flow computed via fast Laplacian solvers becomes a basic primitive that, when wrapped in a multiplicative weights iterative scheme… | ||
| Subsampled Power Iteration: A Unified Algorithm for Block Models and Planted CSP's | Santosh Vempala | 58m |
Proposes Subsampled Power Iteration that partitions edges into ~10 log n independent subgraphs and runs power iteration on each, taking independent subsamples… | ||
| Sketching as a Tool for Numerical Linear Algebra | David P. Woodruff | 01h 03m |
Shows concrete sketching recipes and runtime guarantees: Gaussian JL needs K = Θ(d/ε²) but is dense; a fast JL (Hadamard+sign+sampling) gives O(nd log n) time… | ||
| The Sketching Complexity of Graph Cuts | Alexandr Andoni | 01h 06m |
Claim: any graph-format sparsifier that preserves all cuts needs n/ε^2 lower bound edges, but allowing a non-graph sketch of size O(n/ε polylog n) with a… | ||
| L_p Row Sampling by Lewis Weights | Richard Peng | 01h 02m |
Claims a practical method to sample rows so A' preserves ||Ax||_p for all x by sampling with Lewis weights, shows existence and fast computation, and proves L1… | ||
| You can be a World Champion! | Sivan Toledo | 37m |
A community-run implementation challenge proposes to turn fast theoretical Laplacian solvers into working software by running teams against public matrix… | ||
| Empirical Complexity of Laplacian Solvers: A Discussion | Jon Gilbert | 26m |
Theory gives nearly-linear solvers but implementations remain rough: a published code uses Steiner preconditioners plus multigrid-style layers, hand‑coded… | ||
| Gaussian Free Fields and Computing the Cover Time | James Lee | 01h 02m |
Proves that cover time is captured by the Gaussian free field: cover time ≍ |E| · E[max(GFF)]^2 up to small error terms and universal constants, implying… | ||
| Characterization of Cutoff for Reversible Markov Chains, and Surprise Probabilities | Yuval Peres | 58m |
Proves a sharp inequality: t_mix(2ε) ≤ hit_{1/2}(ε) + C t_rel log(1/ε), and deduces that for lazy reversible chains on trees the product condition (t_rel =… | ||
| Faster Spectral Algorithms via Approximation Theory | Nisheeth Vishnoi | 01h 03m |
Uniform polynomial approximations turn matrix powers into O(M · D) work and give X^S approximants of degree about sqrt(S)·log(1/δ), so S-step walks and… | ||
| Generalized Cheeger Inequalities and Constrained Clustering | Ioannis Koutis | 49m |
Ioannis Koutis, University of Puerto Rico
Fast Algorithms via Spectral Methods
http://simons.berkeley.edu/talks/ioannis-koutis-2014-12-03 | ||
| Solving $1$-Laplacians of Convex Simplicial Complexes | Gary Miller | 56m |
Proposal: fast solver for 1‑Laplacians on certain 3D simplicial complexes that reduce to zero-Laplacian problems via dualization. Method: use Helmholtz… | ||
| First-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms | Lorenzo Orecchia | 01h 05m |
First-order iterative methods combine multiplicative weight updates and gradient descent (plus regularizers like entropy or sqrt(p)) to convert Laplacian-based… | ||
| A Faster Algorithm for Linear Programming and the Maximum Flow Problem I | Yin Tat Lee | 45m |
Presents a new interior‑point framework that replaces the log barrier with a regularized volumetric (joint‑ellipsoid) barrier computable via Lewis weights / Lp… | ||
| A Faster Algorithm for Linear Programming and the Maximum Flow Problem II | Aaron Sidford | 01h 01m |
Claims a linear‑program interior‑point scheme that keeps Renegar‑style cheap iterations while matching the near‑optimal central‑path convergence (roughly √n… | ||
| Fast Flow Algorithms via Cut-Approximators | Jonah Sherman | 59m |
Claims a nearly-linear M^{1+o(1)} randomized algorithm for approximate undirected max‑flow by reducing flow construction to checking a compact… | ||
| Cut-Approximators, Approximating Undirected Max Flows, and Recursion | Richard Peng | 42m |
Presents a concrete recursive recipe that yields a nearly‑linear time (1+ε)-approximation for undirected max flow by combining alpha cut approximator trees… | ||
| nothing matches | ||