BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Ronald de Wolf (CWI and Universiteit van Amsterdam)
DTSTART:20200910T130000Z
DTEND:20200910T135500Z
DTSTAMP:20260423T004137Z
UID:HAC/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/HAC/2/">Effi
 cient algorithms for graph sparsification</a>\nby Ronald de Wolf (CWI and 
 Universiteit van Amsterdam) as part of Heilbronn Annual Conference 2020\n\
 n\nAbstract\nGraphs occur everywhere in discrete mathematics\, but also in
  practical problems in logistics\, the internet\, social networks\, etc. S
 parse graphs (i.e.\, ones with few edges) are easier to handle than dense 
 graphs: they take less space to store and are often cheaper to compute on.
  A long line of work by Karger\, Spielman\, Teng\, and others resulted in 
 nearly-linear-time algorithms that can sparsify any given n-vertex graph G
  to another n-vertex graph H whose number of edges is only O(n)\, while pr
 eserving many important properties of G. This then gives nearly-linear-tim
 e algorithms for solving various cut problems in graphs\, for graph partit
 ioning\, and for solving Laplacian linear systems. We will describe these 
 developments\, and end with our recent work with Simon Apers showing that 
 *quantum* algorithms can even compute such a good graph sparsification in 
 sublinear time.\n
LOCATION:https://researchseminars.org/talk/HAC/2/
END:VEVENT
END:VCALENDAR