A List of Papers on

Computational Complexity at Higher Types
and Related Topics

Version 2.0 – 29 July 1999
with sporadic updates since then
(Version 3 will be out one of these days.)

The following was originally built from the list of papers for my Spring 97 course Computation and Complexity at Higher Types. It is incomplete, out of date, biased towards my interests, and the categories & categorization are rather arbitary, but the list may still be of use.


Papers before 1989

Studies of the Basic Feasible Functionals and Related Classes

Characterizing Complexity Classes via Categorical Constructs, Lambda-Calculi, Logics, and, most especially, Types

There is too much recent work here for a comprehensive list. So, just some of the earlier papers are listed below. See for a recent survey. Also see the home page of the International Workshop on Implicit Computational Complexity, a continuing series of workshops on this and related topics.

Using Types to Build Higher-Type Functionals over Polynomial-Time

Other Papers of Interest

Supplementary Books

Meetings of Interest


In fashion then as of a snow-white rose, Displayed iself to me the saintly host. (Paradiso XXXI, 1,2)
Dante and Beatrice contemplate higher types
and computational complexity
(notice all the big-Os)

Charon the demon, with the eyes of glede, 
Beckoning to them, collects them all together, 
Beats with his oar whoever lags behind 
 (Inferno III, 109-111)
An example of downward tier coercion
(see the Irwin, Kapron, and Royer papers)

More Dore Illustrations for Dante's Comedy

Acknowledgement and Disclaimer

This material is based in part upon work supported by the National Science Foundation under Grants CCR-9522987 and CCR-0098198.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

Last systematic modification: August 1999