LCC 2005

Seventh International Workshop on
Logic and Computational Complexity

24-25 June 2005   •   Chicago

The Logic and Computational Complexity Workshop (LCC'05) will be held on 24-25 June 2005 in Chicago as a satellite workshop of the Logic in Computer Science Conference (LICS'05).
All talks will be in:

The 9th Floor Digital Cinema Studio (*), School of CTI, DePaul University, 243 South Wabash Ave.

 
PROGRAM
SESSION 1: FRIDAY JUNE 24.     Chair: James Royer
1:30-2:30 INVITED TALK: Higher-Order Matching and Games
Colin Stirling (University of Edinburgh)
2:30-2:50 Synthesis of Quasi-Interpretations
Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen, and Romain Pchoux (LORIA/Nancy)
2:50-3:20 coffee break
 
SESSION 2: FRIDAY JUNE 24.     Chair: Leonid Libkinr
3:20-4:20 INVITED TALK: Queries on Tree-Structured Data: Logical Languages and Their Complexity
Christoph Koch (University of Saarlandes)
The slides (in powerpoint).
4:20-4:40 Computing Monadic Fixed-Points in Linear-Time on Doubly-Linked Data Structures
Steven Lindell (Haverford College)
The full paper (in PDF).
4:40-5:00 Database Reformulation with Integrity Constraints
Rada Chirkova (North Carolina State University) and Michael Genesereth (Stanford University)
The full paper.
 
SESSION 3: SATURDAY JUNE 25.     Chair: Andrei Bulatov
9:00-10:00 INVITED TALK: Choiceless Polynomial Time: Introduction and Update
Andreas Blass (University of Michigan)
The slides (in PDF).
10:00-10:20 Model Extension as a Framework for Solving NP-Hard Search Problems
David Mitchell and Eugenia Ternovska (Simon Fraser University)
10:20-10:50 coffee break
 
SESSION 4: SATURDAY JUNE 25.     Chair: Daniel Leivant
10:50-11:50 INVITED TALK: Higher-order recursion schemes, infinite trees and decidability
Luke Ong (University of Oxford)
11:50-12:10 Quantitative Models and Implicit Complexity
Ugo Dal Lago (University of Bologna) and Martin Hofmann (Ludwig Maximilians University Munich)
The full paper.
12:10-2:00 lunch
 
SESSION 5: SATURDAY JUNE 25.     Chair: Christoph Koch
2:00-3:00 INVITED TALK: Making the Stack Visible: Visibly Pushdown Automata
P. Madhusudan (University of Illinois at Urbana-Champaign)
3:00-3:20 Complexity of Clausal Constraints over Chains
Nadia Creignou (LIF/Marseilles), Miki Hermann (L'Ecole Polytechnique), Andrei Krokhin (University of Durham), and Gernot Salzer (Technical University of Vienna)
The full paper (in PDF).
3:20-3:40 coffee break
 
SESSION 6: SATURDAY JUNE 25.     Chair: Andreas Blass
3:40-4:40 INVITED TALK: Algebra Meets Logic: The Case of Regular Languages
Denis Therien (McGill University)
The slides (in PDF).
4:40-5:00 Feasible Proofs of Matrix Identities with Csanky's Algorithm
Michael Soltys (McMaster University)
The full paper.
                       

REGISTRATION AND ACCOMMODATIONS

LICS/LCC Registration: https://securestore.cti.depaul.edu/LICS2005/
Local Information: http://lics.cs.depaul.edu/





Program committee

Steering committee

Important dates

20 May 2005 Early registration deadline
24-25 June 2005 LCC Workshop Dates
26-29 June 2005 LICS'03 Dates

WWW-pages

The LCC home page: http://www.cis.syr.edu/~royer/lcc/
The LICS home page: http://www.lfcs.informatics.ed.ac.uk/lics

Contact information

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

Note on the room assignment
The room assignment is subject to last minuite changes.
If there is a room change, there will be plenty of notices at the workshop site.