• BRICS homepage.

In addition to longer term research activities, BRICS concentrates on one research theme each year. It is intended that each programme includes lecture courses, seminars and workshops suitable both for graduate students and more senior researchers. This year's programme is Proofs and Complexity. See below for a more detailed exposition of this year's theme.

Responsible for this year's theme are Carsten Butz (BRICS), Ulrich Kohlenbach (BRICS), Søren Riis (BRICS), and Glynn Winskel (BRICS).

The main activity will be the workshop Proof Theory and Complexity held August 3-7, 1998. In addition to the locals the following people agreed to participate in the program committee: Stephen Cook (Toronto), Jan Krajícek (Prague and Oxford), Grigori Mints (Stanford), Helmut Schwichtenberg (München), Anne Troelstra (Amsterdam).

Besides the workshop there are several other activities that are related to the theme, for example...

• The course by Ulrich Kohlenbach on Proof Interpretations.
• Our ongoing logic seminar.
• Visitors at BRICS.

• General Information:
  • Information about Aarhus
  • Address

During the last years the connections between proof theory and theoretical computer science have become more and more intensive in both directions: proof theoretic techniques are central tools in e.g. logic programming, verification of programs, automated theorem proving, studies of resource sensitive reasoning etc. In the other direction questions in complexity theory have stimulated new developments in the study of proofs and proof systems.

The theme Proofs and Complexity intends to disseminate technical tools and results of this complexity-oriented approach to proof-transformations and proof systems at BRICS. One of the major aims is to create joint research activities between visitors and researchers at BRICS.

We intend to invite a number of researchers to visit BRICS for an extended period (in July-August 98) and to organize a workshop as the central activity. We expect the visitors to give mini-courses suited for the BRICS PhD students on relevant aspects of the theme and to engage in joint research with BRICS researchers.

Time and Place

The workshop will take place in the first week of August, that is, August 3-7, 1998 here in Aarhus.

Scope of the Workshop

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.

Program Committee

Carsten Butz (BRICS),
Stephen Cook (Toronto),
Ulrich Kohlenbach (BRICS),
Jan Krajícek (Prague and Oxford),
Grigori Mints (Stanford),
Søren Riis (BRICS),
Helmut Schwichtenberg (München),
Anne Troelstra (Amsterdam).

• The course by Ulrich Kohlenbach on Proof Interpretations.
• Our ongoing logic seminar.
• Visitors at BRICS.
• Workshop on Normalization by Evaluation, May 8-9, 1998.
  Organizers: Olivier Danvy and Peter Dybjer.

Information about Aarhus

Aarhus is the second largest town in Denmark with about 250,000 inhabitants. The university campus is located within 10-15 minutes walk from downtown. Today the University of Aarhus has about 18,000 students and 3,000 employees. The University of Aarhus provides more detailed information .

BRICS, is a research center funded by the Danish National Research Foundation. In addition to the research center there is the (formally independent) BRICS PhD School, which provides a PhD program in computer science. Each year the PhD school admits 10-12 new students. The PhD school intends to provide an international graduate school in Denmark. It offers a program of courses and projects of highest scientific quality. The school is open to applications from Danish as well as foreign PhD students. It provides an excellent research environment and scientific training facilities, and aims at making its PhD graduates attractive for a wide spectrum of employers - in private and public research and development institutions, both in Denmark and abroad

Address

Proofs and Complexity `98
BRICS, Department of Computer Science
University of Aarhus
Building 540, Ny Munkegade
DK-8000 Aarhus C, Denmark

WWW: http://www.brics.dk/Activities/98/PAC/ (this page)
Email: Not available. In case you want to get in contact with us please mail to one of the responsibles: Carsten Butz, Urlich Kohlenbach, Søren Riis, and Glynn Winskel.