BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of California\, Berkeley//UCB Events Calendar//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
DTSTART:19701029T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:19700402T020000
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20190429T063603Z
DTSTART;TZID=America/Los_Angeles:20190501T150000
DTEND;TZID=America/Los_Angeles:20190501T160000
TRANSP:OPAQUE
SUMMARY:Rapidly mixing random walks on matroids and related objectsidly mixing random walks on matroids and related objects
UID:125543-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:1011 Evans Hall
DESCRIPTION:Nima Anari\, Stanford University\n\nA central question in randomized algorithm design is what kind of distributions can we sample from efficiently? On the continuous side\, uniform distributions over convex sets and more generally log-concave distributions constitute the main tractable class. We will build a parallel theory on the discrete side\, that yields tractability for a large class of discrete distributions. We will use this theory to resolve a 30-year-old conjecture of Mihail and Vazirani that matroid polytopes have edge expansion at least 1. We will also obtain simple nearly-linear time algorithms for sampling from spanning trees of a graph\, and easy-to-implement algorithms for volume-based sampling.\nThe hammer enabling these algorithmic advances is the introduction and the study of a class of polynomials\, that we call completely log-concave. We can use very simple and easy-to-implement random walks to perform the task of sampling\, and we will use completely log-concave polynomials to analyze the random walk. Based on joint work with Kuikui Liu\, Shayan Oveis Gharan\, Cynthia Vinzant.
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=125543&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20190429T063603Z
LAST-MODIFIED:20190429T063603Z
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR