BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CMSA
X-ORIGINAL-URL:https://cmsa.fas.harvard.edu
X-WR-CALDESC:Events for CMSA
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20180311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20181104T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20190310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20191103T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20200308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20201101T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20210314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20211107T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20190426T143000
DTEND;TZID=America/New_York:20200426T153000
DTSTAMP:20260508T004101
CREATED:20240212T100818Z
LAST-MODIFIED:20240221T092817Z
UID:10001958-1556289000-1587915000@cmsa.fas.harvard.edu
SUMMARY:4/26/2019 General Relativity Seminar
DESCRIPTION:
URL:https://cmsa.fas.harvard.edu/event/4-26-2019-general-relativity-seminar/
LOCATION:MA
CATEGORIES:General Relativity Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20200228T164500
DTEND;TZID=America/New_York:20200228T174500
DTSTAMP:20260508T004101
CREATED:20240212T082705Z
LAST-MODIFIED:20240507T203156Z
UID:10001889-1582908300-1582911900@cmsa.fas.harvard.edu
SUMMARY:Derandomizing Algorithms via Spectral Graph Theory
DESCRIPTION:Speaker: Salil Vadhan (Harvard) \nTitle: Derandomizing Algorithms via Spectral Graph Theory\n\nAbstract: Randomization is a powerful tool for algorithms; it is often easier to design efficient algorithms if we allow the algorithms to “toss coins” and output a correct answer with high probability.  However\, a longstanding conjecture in theoretical computer science is that every randomized algorithm can be efficiently “derandomized” — converted into a deterministic algorithm (which always outputs the correct answer) with only a polynomial increase in running time and only a constant-factor increase in space (i.e. memory usage).  In this talk\, I will describe an approach to proving the space (as opposed to time) version of this conjecture via spectral graph theory.  Specifically\, I will explain how randomized space-bounded algorithms are described by random walks on directed graphs\, and techniques in algorithmic spectral graph theory (e.g. solving Laplacian systems) have yielded deterministic space-efficient algorithms for approximating the behavior of such random walks on undirected graphs and Eulerian directed graphs (where every vertex has the same in-degree as out-degree).  If these algorithms can be extended to general directed graphs\, then the aforementioned conjecture about derandomizing space-efficient algorithms will be resolved.\nJoint works with Jack Murtagh\, Omer Reingold\, Aaron Sidford\,  AmirMadhi Ahmadinejad\, Jon Kelner\, and John Peebles.
URL:https://cmsa.fas.harvard.edu/event/3-4-2020-colloquium/
LOCATION:CMSA\, 20 Garden Street\, Cambridge\, MA\, 02138\, United States
CATEGORIES:Colloquium
ATTACH;FMTTYPE=image/png:https://cmsa.fas.harvard.edu/media/CMSA-Colloquium-03.04.20-1.png
END:VEVENT
END:VCALENDAR