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:20260404T132232Z UID:HAC/2 DESCRIPTION:Title: Efficient algorithms for graph sparsification\nby Ronald de Wolf (C WI 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. Sparse 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 comp ute on. A long line of work by Karger\, Spielman\, Teng\, and others resul ted 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)\, w hile preserving many important properties of G. This then gives nearly-lin ear-time algorithms for solving various cut problems in graphs\, for graph partitioning\, and for solving Laplacian linear systems. We will describe these developments\, and end with our recent work with Simon Apers showin g that *quantum* algorithms can even compute such a good graph sparsificat ion in sublinear time.\n LOCATION:https://stable.researchseminars.org/talk/HAC/2/ END:VEVENT END:VCALENDAR