BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum Speedup for Graph Sparsification\, Cut Approximation and L
 aplacian Solving - Simon Apers\, INRIA and CWI
DTSTART:20191108T120000Z
DTEND:20191108T130000Z
UID:TALK131587@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:Graph sparsification underlies a large number of algorithms\, 
 ranging from approximation algorithms for cut problems to solvers for line
 ar systems in the graph Laplacian. In its strongest form\, “spectral spa
 rsification” reduces the number of edges to near-linear in the number of
  nodes\, while approximately preserving the cut and spectral structure of 
 the graph. The breakthrough work by Benczúr and Karger (STOC’96) and Sp
 ielman and Teng (STOC’04) showed that sparsification can be done in time
  near-linear in the number of edges of the original graph\, which is optim
 al.\n\nIn this work we show that quantum algorithms allow to polynomially 
 speed up spectral sparsification\,\nand thereby many of the derived algori
 thms. The algorithm builds on a string of existing results\, most notably 
 sparsification algorithms by Spielman and Srivastava (STOC’08) and Kouti
 s and Xu (TOPC’16)\, a spanner construction by Thorup and Zwick (STOC’
 01)\, the single-source shortest-paths quantum algorithm by Dürr et al. (
 ICALP’04) and an efficient k-wise independent hash construction by Chris
 tiani\, Pagh and Thorup (STOC’15). Combining our sparsification algorith
 m with existing classical algorithms yields quantum speedups for approxima
 ting the max cut\, min cut\, min st-cut\, sparsest cut and balanced separa
 tor of a graph. Combining our algorithm with a classical Laplacian solver\
 , we demonstrate speedups for Laplacian solving\, for approximating effect
 ive resistances\, cover times\, eigenvalues and eigenvectors of the Laplac
 ian\, and for spectral clustering.\n\nThis is joint work with Ronald de Wo
 lf.
LOCATION:MR15\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR