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.


Surveys



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



Illustrations



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.

http://www.cis.syr.edu/~royer/
Last systematic modification: August 1999