MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A Type System for Incremental Computational Complexity

Ezgi Cicek
Max Planck Institute for Software Systems
SWS Student Defense Talks - Qualifying Exam
SWS  
Expert Audience
English

Date, Time and Location

Thursday, 13 February 2014
14:00
60 Minutes
E1 5
029
Saarbrücken

Abstract

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.

Contact

--email hidden
passcode not visible
logged in users only

Maria-Louise Albrecht, 03/04/2014 13:05
Maria-Louise Albrecht, 02/27/2014 14:57
Maria-Louise Albrecht, 02/26/2014 11:48 -- Created document.