SUMMARIES OF TALKS FROM THE
DIMACS Workshop on Computational
Complexity
and Programming Languages
The aim of the workshop was to bring together researchers in
computational complexity and in programming languages to work toward
deepening the interplay between the two areas. The workshop
included a series of invited talks on a broad range of topics and a
series of open contributed talks by workshop participants. 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

Semanticallybased costmodels 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 type2 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 type3 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 categorytheoretic proof that
PV_{omega} = 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