Abstract: Implicit computational complexity is the study of
(elegant) machine-independent characterizations of traditional
complexity classes such as the polynomial-time computable functions.
A sometimes-stated hope is that such results could yield programming
languages with the pleasant properties that (1) any compilable
program lies in the characterized complexity class, and (2) there is
a program for any function in the complexity class. The reality,
though, is that while a complexity class may be captured, many
natural *algorithms* are not. For example, many characterizations of
polynomial-time exclude precisely the kinds of recursive definitions
used in insertion- and selection-sort. In this talk I will discuss
current work with James Royer of Syracuse University on a functional
language which captures exactly the type-2 polynomial-time computable
functionals and at the same time allows for fairly natural
programming. This talk will be longer on motivation and examples and
shorter on proofs.