LCC'11 MEETING
The Twelfth International Workshop on Logic and Computational Complexity
(LCC'11, http://www.cs.swansea.ac.uk/lcc2011/)
will be held in Toronto on June 25, 2011, as an affiliated meeting
of LiCS'11.
LCC meetings are aimed at the foundational interconnections between
logic and computational complexity, as present, for example, in
implicit computational complexity (descriptive and typetheoretic methods);
deductive formalisms as they relate to complexity (e.g. ramification,
weak comprehension, bounded arithmetic, linear logic and resource logics);
complexity aspects of finite model theory and databases;
complexitymindful program derivation and verification;
computational complexity at higher type; and proof complexity.
The LCC'11 program will consist of invited lectures as well as
contributed papers selected by the program committee.
Registration for LCC'11 jointly with LiCS can be done via the
LiCS web page.
Registration for LCC alone will be enabled soon.
INVITED SPEAKERS
PROGRAMME
9:00 9:55 M. Braverman: Computability and Complexity of Julia Sets (invited talk)
9:5510:20 P. Nguyen: Feasible Interpolation for Lifted Segments [pdf]
10:2010:45 D.T.M. Le, S. Cook and Y. Ye: A Formal Theory for the Complexity Class
Associated with Stable Marriage Problem [pdf]
10:4511:00 Break
11:0011:55 P. Tesson: The expressive power of twovariable logics over words (invited talk)
11:5512:20 N. Ackerman, C.E. Freer and D.M. Roy: #PComplete Conditional Distributions [pdf]
12:2013:20 Lunch
13:2013:45 P. Baillot: On Elementary Linear Logic and Polynomial Time [pdf]
13:4514:40 I. Oitavem: Monotone recursion versus monotone iteration within FPSPACE
(invited talk) [pdf]
14:4015:05 U. Dal Lago and P.P. Toldin: A Higher Order Characterization of Probabilistic
Polynomial Time [pdf]
15:0515:20 Break
15:2015:45 Y. Filmus and T. Pitassi: Lower Bounds for Cutting Planes [pdf]
15:4516:10 M. Gwynne and O. Kullmann: Attacking DES + AES via SAT: Constraints and
boolean functions [pdf]
16:1016:35 S. Siebertz and E. Grädel: Dynamic Definability [pdf]
16:3517:00 R.J. Lipton and K. Regan: A FiniteCompactness Notion, and Property Testing [pdf]
PROGRAM COMMITTEE
 Ulrich Berger (Swansea, CoChair)
 Denis Therien (McGill Montreal, CoChair)
 Klaus Aehlig (Southampton)
 Arnold Beckmann (Swansea)
 Guillaume Bonfante (LORIA Nancy)
 Ugo Dal Lago (Bologna)
 Phuong Nguyen (McGill Montreal)
 Luca Roversi (Torino)
 Thomas Schwentick (TU Dortmund)
 Howard Straubing (Boston College)
 Kazushige Terui (Kyoto)
 Heribert Vollmer (Hanover)
STEERING COMMITTEE
 Michael Benedikt (Oxford, Cochair)
 Daniel Leivant (Indiana U, Cochair)
 Robert Constable (Cornell)
 Anuj Dawar (Cambridge)
 Fernando Ferreira (Lisbon)
 Martin Hofmann (U Munich)
 Neil Immerman (U Mass. Amherst)
 Neil Jones (Copenhagen)
 Bruce Kapron (U Victoria)
 Stefan Kreutzer (Oxford)
 JeanYves Marion (LORIA Nancy)
 Luke Ong (Oxford)
 Martin Otto (Darmstadt)
 Simona Ronchi de la Rocca (Turin)
 James Royer (Syracuse)
 Helmut Schwichtenberg (U Munich)
 Pawel Urzyczyn (Warsaw)
