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
-
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