This page, and any PDF documents linked on this page, are no longer maintained and may not meet accessibility standards. To request an accessible version of any content, please contact us.
SUMMARIES OF TALKS FROM THE
DIMACS Workshop on Computational
Complexity
For more background on the workshop, click
here.
The following is a list of both series of talks. In the
list:
Clicking on a title sends you to a summary of the talk.
Clicking on a speaker's name sends you to contact and
home page information on the speaker.
Invited Talks
Computability and complexity from a
programming perspective ,
Neil D. Jones,
DIKU, University of Copenhagen
Semantically-based cost-models and
provably efficient implementations ,
Guy Blelloch,
School of Computer Science, Carnegie Mellon University
Lazy functional programming languages and
persistent amortized data structures ,
Chris Okasaki,
School of Computer Science, Carnegie Mellon University
Complexity and optimal reduction ,
Harry Mairson,
Department of Computer Science, Brandeis University
Polynomial time type-2 computation ,
Bruce M. Kapron ,
Department of Computer Science, University of Victoria
Feasibility in higher types ,
Daniel Leivant ,
Computer Science Department, Indiana University
Berry and Curien's intensional legacy ,
Denis Dancanet ,
School of Computer Science, Carnegie Mellon University
Intensional semantics, abstract interpretation
and complexity estimates ,
Eugenio Moggi ,
Dipartimento di Informatica, University of Genova
Intensional semantics and complexity ,
Samson Abramsky ,
Department of Computer Science, Edinburgh University
Contributed Talks
A feasible type-3 functional that fails to be basic
feasible ,
James S. Royer ,
School of Computer and Information Science, Syracuse University
Computational models based on explicit substitution with an
address oracle using parallel reduction ,
Kristoffer H. Rose ,
BRICS, University of Aarhus
Characterizing computation models with a
constant factor time hierachy ,
Eva Rose ,
DIKU, University of Copenhagen
A category-theoretic proof that
PVomega = PTIME ,
Martin Hofmann ,
Fachbereich Mathematik, Technische Hochschule Darmstadt
Half tiers and linear space (and time) ,
James Otto
Explicit process locations and functional parallel
programming ,
Gaétan Hains ,
LIFO, Université d'Orléans