Overview

The synergy between Logic and Computational Complexity has gained importance and vigor in recent years, cutting across areas such as Proof Theory, Finite Model Theory, Computation Theory, Applicative Programming, Database Theory, and Philosophical Logic. Several machine-independent approaches to computational complexity have been developed that are based on notions stemming from mathematical logic, programming language theory, and database theory. Examples include descriptive complexity (finite model theory), bounded arithmetic, set-existence principles, intrinsic theories, linear logics, and algebras of functions. Collectively these approaches might be termed Implicit Computational Complexity. Practically, implicit computational complexity provide a framework for a principled incorporation of computational complexity into areas such as formal methods in software development, the study of programming languages, and database theory, and principles of programming and database languages. The workshop aims at furthering an understanding of the fundamental relations between computational complexity and logic.

Program

• LCC program
• LCC accepted papers (updated)

Format

The program will consist of sessions of contributed papers, invited talks, and software demonstrations.

Topics

• complexity analysis for functional languages
• complexity in database theory
• complexity in formal methods
• computational complexity in higher types
• formal methods for complexity analysis of programs
• foundations of implicit computational complexity
• logical & machine-independent characterizations of complexity classes
• logics closely related to complexity classes
• proof complexity
• semantic approaches to complexity
• software that applies LCC ideas
• type systems for controlling complexity

Program Committee

• Georg Gottlob (University of Oxford)
• Neil Immerman (University of Massachusetts, Amherst) co-chair
• Russell Impagliazzo (University of California, San Diego)
• Neil Jones (University of Copenhagen)
• Bruce Kapron (University of Victoria) co-chair
• Harry Mairson (Brandeis University)
• Karl-Heinz Niggl (University of Technology, Ilmenau)
• Toniann Pitassi (University of Toronto)
• Thomas Schwentick (University of Dortmund)
• Colin Stirling (University of Edinburgh)

Steering committee

• Anuj Dawar (University of Cambridge)
• Fernando Ferreira (University of Lisbon)
• Martin Hoffmann (Ludwig Maximilians University Munich)
• Neil Jones (University of Copenhagen)
• Bruce Kapron (University of Victoria)
• Daniel Leivant (Indiana University)
• Jean-Yves Marion (LORIA/Nancy)
• Luke Ong (University of Oxford)
• James Royer (Syracuse University), chair
• Helmut Schwichtenberg (Ludwig Maximilians University Munich)

Contact information

James S. Royer
Department of Electrial Engineering and Computer Science
Syracuse University
Syracuse, NY 13244 USA
Email: royer at ecs syr edu