LICS Program
W1
Implicit computational complexity
Program

 

June 30, 1999 -  Room 7-L
9:00 -9:05

 Welcome
9:05 -9:55 The ordered conjecture: a status report
Phokion Kolaitis (UC Santa Cruz)
COFFEE and REFRESHMENTS
10:15 - 11:05 The complexity of acyclic conjunctive queries
Georg Gottlob (TU Wien)
Abstract
11:15 - 12:05 Choiceless Polynomial Time
Yuri Gurevich (Microsoft Research)
12:10 - 12:35 Light multiset path ordering and PTime: Two is better than one
Jean-Yves Marion (Nancy)
LUNCH
JOINT SESSION ON FINITE MODEL THEORY
13:50 - 14:40 Dynamic Reachability
Neil Immerman (U. Mass)
14:50 -15:40 The Linear Order in Descriptive Complexity Theory
Thomas Schwentick (U. Mainz)
COFFEE and REFRESHMENTS
16:10 - 17:00 Topological Queries in Spatial Databases
Victor Vianu (UC San Diego)
17:10 - 18:00 Complexity in AI and Knowledge Representation
Christos Papadimitriou (UC Berkeley)
20:00 RECEPTION (tentative)

(joint with FLoC workshop 14, Finite Model Theory and its Applications)

July 1, 1999 -  Room 7-L
9:00 -9:50

 The expressive power of higher-order types or, life without CONS
Neil Jones (DIKU)
Abstract
COFFEE and REFRESHMENTS
10:15 - 11:05 A survey of feasibility in higher types
Anil Seth (Inst. Math. Sci., Madras)
Abstract
11:15 - 12:05 Higher type recursion, ramification and polynomial time
(research joint with S. Bellantoni and K.-H. Niggl)
Helmut Schwichtenberg (Munich)
Abstract
12:10 -12:35 Predicative recursion, contructive diagonalization and the elementary functions
Salvatore Caporaso, Giovanni Pani and Emanuele Covino (Bari)
Abstract
LUNCH
14:00 -14:50 Type systems for polynomial time
Martin Hofmann (Edinburgh)
Abstract
15:00 - 15:25 An upper bound on the derivation complexity of Knuth-Bendix orderings
Dieter Hofbauer (Kassel)
COFFEE and REFRESHMENTS
15:50 - 16:40 Linear logic and computational complexity
Jean-Yves Girard (Marseille)
17:00 - 17:25 Elementary recursive functions and linear logic
Vincent Danos (Paris 7 and CNRS) and Jean-Baptiste Joinet (Paris 7)
Abstract
REFRESHMENTS
17:45 - 18:35 The descriptive complexity of constraint satisfaction
Moshe Y. Vardi (Rice)
Abstract

Program