James S. Royer


  • Ph. D.

Research Interests:

  • Computational complexity of higher type functions and operators
  • Computational complexity over inductively and coinductively defined data
  • Implicit computational complexity
  • Complexity theoretically motivated type systems
  • Formal certification of time and space bounds on programs

Current Research:

James Royer works in the theory of computation. He is probably best known for his work in structural complexity theory (particularly the structure of complete degrees and one-way functions). He has also worked on learning theory, biological computing, and classical computability theory. His current work is on the computational complexity of higher-type operators and functionals with the applications of this theory to problems in programming languages. In particular, he is interested in developing type systems and compositional semantics to support reasoning about time and space usage in programming languages such as Haskell and ML.

Courses Taught:

  • Type Theory
  • Programming Language
  • Functional programming
  • Data Structures

Selected Publications:

On the Computational Complexity of Longley’s H Functional, by James S. Royer, Theoretical Computer Science 318 (2004) 225-241.

Generality’s Price: Inescapable Deficiencies in Machine-Learned Programs, by John Case, Keh-Jiann Chen, Sanjay Jain, Wolfgang Merkle, and Jim Royer, Annals of Pure and Applied Logic 139 (2006) 303–326.

Adventures in time and space, by Norman Danner and James. S. Royer, Logical Methods in Computer Science, 3:9 (2007) 1–53.

Two algorithms in search of a type system, by Norman Danner and James. S. Royer, Theory of Computing Systems 45 (2009) 787–821.

A static cost analysis for a higher-order language, by Norman Danner, Jennifer Paykin, and James. S. Royer, to appear in Programming Languages meets Program Verification 2013, 2013.