Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Type System for Incremental Computational Complexity
Speaker:Ezgi Cicek
coming from:Max Planck Institute for Software Systems
Speakers Bio:
Event Type:SWS Student Defense Talks - Qualifying Exam
We use this to send out email in the morning.
Level:Expert Audience
Date, Time and Location
Date:Thursday, 13 February 2014
Duration:60 Minutes
Building:E1 5
With recent advances in incremental computation, programs can be
compiled to automatically respond to incremental input changes.
However, there is no language-level support for reasoning about
the asymptotic time complexity of incremental updates. Motivated

by this gap, we equip a list-processing language with a cost-accounting
semantics and a type system for compositionally proving the
complexity of such updates. Our type system includes novel
refinements that bound changes to inputs and captures dynamic stability,
a measure of the time required to re-run a program, given the
trace of an earlier execution with boundedly different inputs. Effectively,
our type system proves a computational continuity property
that bounds not only output changes but also changes to the trace
as a function of input changes. We prove our type system sound
relative to the cost semantics and verify experimentally that the
cost semantics is realistic in practice.

Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Maria-Louise Albrecht, 03/04/2014 01:05 PM
  • Maria-Louise Albrecht, 02/27/2014 02:57 PM
  • Maria-Louise Albrecht, 02/26/2014 11:48 AM -- Created document.