BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Quantum Speedup for Graph Sparsification\, Cut App
roximation and Laplacian Solving - Simon Apers\, I
NRIA and CWI
DTSTART;TZID=Europe/London:20191108T120000
DTEND;TZID=Europe/London:20191108T130000
UID:TALK131587AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/131587
DESCRIPTION:Graph sparsification underlies a large number of a
lgorithms\, ranging from approximation algorithms
for cut problems to solvers for linear systems in
the graph Laplacian. In its strongest form\, “spec
tral sparsification” reduces the number of edges t
o near-linear in the number of nodes\, while appro
ximately preserving the cut and spectral structure
of the graph. The breakthrough work by Benczúr an
d Karger (STOC’96) and Spielman and Teng (STOC’04)
showed that sparsification can be done in time ne
ar-linear in the number of edges of the original g
raph\, which is optimal.\n\nIn this work we show t
hat quantum algorithms allow to polynomially speed
up spectral sparsification\,\nand thereby many of
the derived algorithms. The algorithm builds on a
string of existing results\, most notably sparsif
ication algorithms by Spielman and Srivastava (STO
C’08) and Koutis and Xu (TOPC’16)\, a spanner cons
truction by Thorup and Zwick (STOC’01)\, the singl
e-source shortest-paths quantum algorithm by Dürr
et al. (ICALP’04) and an efficient k-wise independ
ent hash construction by Christiani\, Pagh and Tho
rup (STOC’15). Combining our sparsification algori
thm with existing classical algorithms yields quan
tum speedups for approximating the max cut\, min c
ut\, min st-cut\, sparsest cut and balanced separa
tor of a graph. Combining our algorithm with a cla
ssical Laplacian solver\, we demonstrate speedups
for Laplacian solving\, for approximating effectiv
e resistances\, cover times\, eigenvalues and eige
nvectors of the Laplacian\, and for spectral clust
ering.\n\nThis is joint work with Ronald de Wolf.
LOCATION:MR15\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Johannes Bausch
END:VEVENT
END:VCALENDAR