<span itemscope itemtype="http://schema.org/InformAction"><span style="display:none" itemprop="about" itemscope itemtype="http://schema.org/Person"><meta itemprop="description" content="Invitation from julianbrunner@gmail.com"/></span><span itemprop="object" itemscope itemtype="http://schema.org/Event"><div style=""><table cellspacing="0" cellpadding="8" border="0" summary="" style="width:100%;font-family:Arial,Sans-serif;border:1px Solid #ccc;border-width:1px 2px 2px 1px;background-color:#fff;"><tr><td><meta itemprop="eventStatus" content="http://schema.org/EventScheduled"/><h4 style="padding:6px 0;margin:0 0 4px 0;font-family:Arial,Sans-serif;font-size:13px;line-height:1.4;border:1px Solid #fff;background:#fff;color:#090;font-weight:normal"><strong>You have been invited to the following event.</strong></h4><div style="padding:2px"><span itemprop="publisher" itemscope itemtype="http://schema.org/Organization"><meta itemprop="name" content="Google Calendar"/></span><meta itemprop="eventId/googleCalendar" content="5rpa5p28pg9pek61ht4d20d5md"/><div style="float:right;font-weight:bold;font-size:13px"> <a href="https://www.google.com/calendar/event?action=VIEW&eid=NXJwYTVwMjhwZzlwZWs2MWh0NGQyMGQ1bWQgY2x1YjJAbWFpbGJyb3kuaW5mb3JtYXRpay50dS1tdWVuY2hlbi5kZQ&tok=NTIjc2U2ZWJlM3RvZmY0Y2g1bm11bmlibTVtOThAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbTg1MDNjNjFlZDRkODhiODM5NDFmY2M1M2MwNDA1YmE2M2M2YWFkZWM&ctz=Europe%2FBerlin&hl=en&es=0" style="color:#20c;white-space:nowrap" itemprop="url">more details »</a><br></div><h3 style="padding:0 0 6px 0;margin:0;font-family:Arial,Sans-serif;font-size:16px;font-weight:bold;color:#222"><span itemprop="name">Formal Proof and Analysis of an Incremental Cycle Detection Algorithm</span></h3><table cellpadding="0" cellspacing="0" border="0" summary="Event details"><tr><td style="padding:0 1em 10px 0;font-family:Arial,Sans-serif;font-size:13px;color:#888;white-space:nowrap;width:90px" valign="top"><div><i style="font-style:normal">When</i></div></td><td style="padding-bottom:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222" valign="top"><div style="text-indent:-1px"><time itemprop="startDate" datetime="20190605T120000Z"></time><time itemprop="endDate" datetime="20190605T130000Z"></time>Wed Jun 5, 2019 14:00 – 15:00 <span style="color:#888">Central European Time - Berlin</span></div></td></tr><tr><td style="padding:0 1em 10px 0;font-family:Arial,Sans-serif;font-size:13px;color:#888;white-space:nowrap;width:90px" valign="top"><div><i style="font-style:normal">Where</i></div></td><td style="padding-bottom:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222" valign="top"><div style="text-indent:-1px"><span itemprop="location" itemscope itemtype="http://schema.org/Place"><span itemprop="name" class="notranslate">MI 02.07.023</span><span dir="ltr"> (<a href="https://maps.google.com/maps?q=MI+02.07.023&hl=en" style="color:#20c;white-space:nowrap" target="_blank" itemprop="map">map</a>)</span></span></div></td></tr><tr><td style="padding:0 1em 10px 0;font-family:Arial,Sans-serif;font-size:13px;color:#888;white-space:nowrap;width:90px" valign="top"><div><i style="font-style:normal">Calendar</i></div></td><td style="padding-bottom:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222" valign="top"><div style="text-indent:-1px">club2@mailbroy.informatik.tu-muenchen.de</div></td></tr><tr><td style="padding:0 1em 10px 0;font-family:Arial,Sans-serif;font-size:13px;color:#888;white-space:nowrap;width:90px" valign="top"><div><i style="font-style:normal">Who</i></div></td><td style="padding-bottom:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222" valign="top"><table cellspacing="0" cellpadding="0"><tr><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222;width:10px"><div style="text-indent:-1px"><span style="font-family:Courier New,monospace">•</span></div></td><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222"><div style="text-indent:-1px"><div><div style="margin:0 0 0.3em 0"><span class="notranslate">julianbrunner@gmail.com</span><span style="font-size:11px;color:#888"> - creator</span></div></div></div></td></tr><tr><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222;width:10px"><div style="text-indent:-1px"><span style="font-family:Courier New,monospace">•</span></div></td><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222"><div style="text-indent:-1px"><div><div style="margin:0 0 0.3em 0"><span itemprop="attendee" itemscope itemtype="http://schema.org/Person"><span itemprop="name" class="notranslate">puma-alle@lists.tcs.ifi.lmu.de</span><meta itemprop="email" content="puma-alle@lists.tcs.ifi.lmu.de"/></span></div></div></div></td></tr><tr><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222;width:10px"><div style="text-indent:-1px"><span style="font-family:Courier New,monospace">•</span></div></td><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222"><div style="text-indent:-1px"><div><div style="margin:0 0 0.3em 0"><span itemprop="attendee" itemscope itemtype="http://schema.org/Person"><span itemprop="name" class="notranslate">club2@mailbroy.informatik.tu-muenchen.de</span><meta itemprop="email" content="club2@mailbroy.informatik.tu-muenchen.de"/></span></div></div></div></td></tr><tr><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222;width:10px"><div style="text-indent:-1px"><span style="font-family:Courier New,monospace">•</span></div></td><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222"><div style="text-indent:-1px"><div><div style="margin:0 0 0.3em 0"><span itemprop="attendee" itemscope itemtype="http://schema.org/Person"><span itemprop="name" class="notranslate">casasa@in.tum.de</span><meta itemprop="email" content="casasa@in.tum.de"/></span></div></div></div></td></tr><tr><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222;width:10px"><div style="text-indent:-1px"><span style="font-family:Courier New,monospace">•</span></div></td><td style="padding-right:10px;font-family:Arial,Sans-serif;font-size:13px;color:#222"><div style="text-indent:-1px"><div><div style="margin:0 0 0.3em 0"><span itemprop="attendee" itemscope itemtype="http://schema.org/Person"><span itemprop="name" class="notranslate">armael.gueneau@inria.fr</span><meta itemprop="email" content="armael.gueneau@inria.fr"/></span></div></div></div></td></tr></table></td></tr></table><div style="padding-bottom:15px;font-family:Arial,Sans-serif;font-size:13px;color:#222;white-space:pre-wrap!important;white-space:-moz-pre-wrap!important;white-space:-pre-wrap!important;white-space:-o-pre-wrap!important;white-space:pre;word-wrap:break-word"><span>Speaker: Armaël Guéneau<p>Abstract</p><p>In this talk, I will present the analysis of a state-of-the-art incremental cycle detection algorithm due to Bender, Fineman, Gilbert, and Tarjan. The algorithm maintains subtle invariants, and features a highly non trivial asymptotic, amortized complexity bound. We propose a simple change that allows the algorithm to be regarded as genuinely online. Then, I will detail how we exploit Separation Logic with Time Credits to simultaneously verify the correctness and the worst-case amortized complexity of the modified algorithm. This will be the occasion of deeper dives explaining our approach for modular verification of asymptotic complexity using time credits, in the context of the Coq proof assistant.</p><p>This is joint work with Arthur Charguéraud, Jacques-Henri Jourdan and François Pottier.</p></span><meta itemprop="description" content="Speaker: Armaël Guéneau
Abstract
In this talk, I will present the analysis of a state-of-the-art incremental cycle detection algorithm due to Bender, Fineman, Gilbert, and Tarjan. The algorithm maintains subtle invariants, and features a highly non trivial asymptotic, amortized complexity bound. We propose a simple change that allows the algorithm to be regarded as genuinely online. Then, I will detail how we exploit Separation Logic with Time Credits to simultaneously verify the correctness and the worst-case amortized complexity of the modified algorithm. This will be the occasion of deeper dives explaining our approach for modular verification of asymptotic complexity using time credits, in the context of the Coq proof assistant.
This is joint work with Arthur Charguéraud, Jacques-Henri Jourdan and François Pottier."/></div></div><p style="color:#222;font-size:13px;margin:0"><span style="color:#888">Going (club2@mailbroy.informatik.tu-muenchen.de)? </span><wbr><strong><span itemprop="potentialaction" itemscope itemtype="http://schema.org/RsvpAction"><meta itemprop="attendance" content="http://schema.org/RsvpAttendance/Yes"/><span itemprop="handler" itemscope itemtype="http://schema.org/HttpActionHandler"><link itemprop="method" href="http://schema.org/HttpRequestMethod/GET"/><a href="https://www.google.com/calendar/event?action=RESPOND&eid=NXJwYTVwMjhwZzlwZWs2MWh0NGQyMGQ1bWQgY2x1YjJAbWFpbGJyb3kuaW5mb3JtYXRpay50dS1tdWVuY2hlbi5kZQ&rst=1&tok=NTIjc2U2ZWJlM3RvZmY0Y2g1bm11bmlibTVtOThAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbTg1MDNjNjFlZDRkODhiODM5NDFmY2M1M2MwNDA1YmE2M2M2YWFkZWM&ctz=Europe%2FBerlin&hl=en&es=0" style="color:#20c;white-space:nowrap" itemprop="url">Yes</a></span></span><span style="margin:0 0.4em;font-weight:normal"> - </span><span itemprop="potentialaction" itemscope itemtype="http://schema.org/RsvpAction"><meta itemprop="attendance" content="http://schema.org/RsvpAttendance/Maybe"/><span itemprop="handler" itemscope itemtype="http://schema.org/HttpActionHandler"><link itemprop="method" href="http://schema.org/HttpRequestMethod/GET"/><a href="https://www.google.com/calendar/event?action=RESPOND&eid=NXJwYTVwMjhwZzlwZWs2MWh0NGQyMGQ1bWQgY2x1YjJAbWFpbGJyb3kuaW5mb3JtYXRpay50dS1tdWVuY2hlbi5kZQ&rst=3&tok=NTIjc2U2ZWJlM3RvZmY0Y2g1bm11bmlibTVtOThAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbTg1MDNjNjFlZDRkODhiODM5NDFmY2M1M2MwNDA1YmE2M2M2YWFkZWM&ctz=Europe%2FBerlin&hl=en&es=0" style="color:#20c;white-space:nowrap" itemprop="url">Maybe</a></span></span><span style="margin:0 0.4em;font-weight:normal"> - </span><span itemprop="potentialaction" itemscope itemtype="http://schema.org/RsvpAction"><meta itemprop="attendance" content="http://schema.org/RsvpAttendance/No"/><span itemprop="handler" itemscope itemtype="http://schema.org/HttpActionHandler"><link itemprop="method" href="http://schema.org/HttpRequestMethod/GET"/><a href="https://www.google.com/calendar/event?action=RESPOND&eid=NXJwYTVwMjhwZzlwZWs2MWh0NGQyMGQ1bWQgY2x1YjJAbWFpbGJyb3kuaW5mb3JtYXRpay50dS1tdWVuY2hlbi5kZQ&rst=2&tok=NTIjc2U2ZWJlM3RvZmY0Y2g1bm11bmlibTVtOThAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbTg1MDNjNjFlZDRkODhiODM5NDFmY2M1M2MwNDA1YmE2M2M2YWFkZWM&ctz=Europe%2FBerlin&hl=en&es=0" style="color:#20c;white-space:nowrap" itemprop="url">No</a></span></span></strong> <wbr><a href="https://www.google.com/calendar/event?action=VIEW&eid=NXJwYTVwMjhwZzlwZWs2MWh0NGQyMGQ1bWQgY2x1YjJAbWFpbGJyb3kuaW5mb3JtYXRpay50dS1tdWVuY2hlbi5kZQ&tok=NTIjc2U2ZWJlM3RvZmY0Y2g1bm11bmlibTVtOThAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbTg1MDNjNjFlZDRkODhiODM5NDFmY2M1M2MwNDA1YmE2M2M2YWFkZWM&ctz=Europe%2FBerlin&hl=en&es=0" style="color:#20c;white-space:nowrap" itemprop="url">more options »</a></p></td></tr><tr><td style="background-color:#f6f6f6;color:#888;border-top:1px Solid #ccc;font-family:Arial,Sans-serif;font-size:11px"><p>Invitation from <a href="https://www.google.com/calendar/" target="_blank" style="">Google Calendar</a></p><p>You are receiving this courtesy email at the account club2@mailbroy.informatik.tu-muenchen.de because you are an attendee of this event.</p><p>To stop receiving future updates for this event, decline this event. Alternatively you can sign up for a Google account at https://www.google.com/calendar/ and control your notification settings for your entire calendar.</p><p>Forwarding this invitation could allow any recipient to send a response to the organizer and be added to the guest list, or invite others regardless of their own invitation status, or to modify your RSVP. <a href="https://support.google.com/calendar/answer/37135#forwarding">Learn More</a>.</p></td></tr></table></div></span></span>