BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Incrementality xor currency for monotone fixed points - Michael Ar
 ntzenius\, University of Cambridge
DTSTART:20201016T130000Z
DTEND:20201016T140000Z
UID:TALK152581@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION:https://youtu.be/OkX6YKSLNQ0\n\nMany problems can be concisely
  expressed as finding the least fixed point of a monotone map\, including 
 graph reachability\, static analysis by abstract interpretation\, regular 
 expression matching\, and parsing. There is a straightforward way to compu
 te these fixpoints: iterate the function. Unfortunately\, this is ineffici
 ent\, for at least two reasons: first\, it performs redundant work during 
 each iteration\; second\, it is inherently single-threaded.\n\nIn this tal
 k\, I will show how to solve the first of these problems using seminaive e
 valuation\, a technique that iterates to a fixed point faster by computing
  only the differences between iterations. I will also discuss work in prog
 ress on the second problem using a simple graph based model of concurrent 
 monotone computation. Unfortunately\, I do not know how to reconcile these
  two approaches and achieve an implementation strategy for monotone fixed 
 points that is both incremental and concurrent.
LOCATION:Online
END:VEVENT
END:VCALENDAR