Workshop Program: Collegium Logicum Complexity

Subject: Workshop Program: Collegium Logicum Complexity
From: veith (
Date: Thu Sep 03 1998 - 14:07:45 MET DST


        Collegium Logicum 1998: Complexity

        Vienna University of Technology

        October 9-10, 1998


The international workshop COLLEGIUM LOGICUM 1998: COMPLEXITY is intended as
a forum for the exchange of ideas and interaction between researchers working
in computational and logical complexity. The workshop covers different areas of
computer science, logic and mathematics including circuit complexity, structural complexity, proof complexity, finite model theory, bounded arithmetic, and
complexity of information systems.

The workshop is part of the ongoing lecture series COLLEGIUM LOGICUM of
the Kurt Gödel Society. The scientific board of the workshop consists of
M. Baaz and G. Gottlob, present and former general secretaries of the
Kurt Gödel Society.

For further information write to

        --- Preliminary Program -----

Friday, October 9:

 9.00 - 9.45 A. RAZBOROV (to be announced)

10.00 - 10.45 H. BUHRMAN Possible Approaches to separate P from NP

11.15 - 12.00 P. CRESCENZI On the Complexity of Approximating
                                Constraint Satisfaction Problems


14.00 - 14.45 A. LEITSCH Cut Normal Forms and Proof Complexity

15.00 - 15.45 A. BECKMANN Dynamic Ordinal Analysis and Separation for
                                Weak Fragments of Bounded Arithmetic

16.15 - 17.00 A. CARBONE (to be announced)

17.15 - 17.45 K. NIGGL Characterising Polytime Through Higher
                                Type Recursion

Saturday, October 10:

 9.00 - 9.45 J. KRAJICEK Weak Pigeonhole Principle

10.00 - 10.45 Z. SADOWSKI Complexity-Theoretic Consequences of the
                                Existence of Optimal Proof Systems

11.15 - 12.00 T. EITER On the Complexity of Data Disjunctions


14.00 - 14.45 E. GRAEDEL Guarded Fragments of First Order Logic

15.00 - 15.45 M. GROHE Graph Structure Theory and Descriptive

16.00 - 16.45 H. VEITH On the Complexity of Triangular Norms

17.15 - 17.45 L. LIBKIN Logics with Counting, Auxiliary Relations, and
                                 Lower Bounds for Invariant Queries

18.00 - General Assembly of the Kurt Goedel Society
(A seperate announcement will follow.)

This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:20 MET DST