Abstracts of the Workshop on Proof Theory and Complexity,
PTAC '98,
(Aarhus, Denmark, August 3-7, 1998)

Carsten Butz
Ulrich Kohlenbach
Søren Riis
Glynn Winskel

July 1998


This small booklet contains the titles and abstracts of the talks given at the workshop Proof Theory and Complexity (PTAC'98), hosted by BRICS during the first week of August 98 (August 3 - August 7).

The topic of the workshop will be on proof-theory with connections to issues of complexity in the widest sense including e.g.:

  1. Strength (proof-theoretic and mathematical) of subsystems of second-order arithmetic and type theories.
  2. Type-free applicative systems (explicit mathematics).
  3. Complexity of Proof Transformations (cut-elimination, normalization, epsilon-substitution etc.).
  4. Proofs as Programs.
  5. Proof Interpretations and their complexity: Realizability and functional interpretations, game theoretic and categorical interpretations.
  6. Bounded arithmetic and connections to complexity theory (including feasible arithmetic and analysis).
  7. Proof Complexity of propositional proof systems: resolution, Frege systems, Nullstellensatz proofs etc.
  8. Interactive and probabilistic proofs.
There were two preparatory lectures during the week before the workshop (by E. Palmgren and V. Orevkov--abstracts can be obtained from the BRICS homepage), and there are two special lectures in connection with the workshop that take place during this week (by A. Feferman and A. Wigderson)

Available as PostScript, PDF, DVI.


Last modified: 2003-06-04 by webmaster.