Logic and Computational Complexity

An International Workshop Series






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 type-theoretic 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; complexity-mindful 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.



   9:00- 9:55   M. Braverman: Computability and Complexity of Julia Sets (invited talk) 
   9:55-10:20   P. Nguyen: Feasible Interpolation for Lifted Segments [pdf]
  10:20-10:45   D.T.M. Le, S. Cook and Y. Ye: A Formal Theory for the Complexity Class 
                Associated with Stable Marriage Problem [pdf]
  10:45-11:00 Break
  11:00-11:55   P. Tesson: The expressive power of two-variable logics over words (invited talk)
  11:55-12:20   N. Ackerman, C.E. Freer and D.M. Roy: #PComplete Conditional Distributions [pdf]

  12:20-13:20 Lunch

  13:20-13:45   P. Baillot: On Elementary Linear Logic and Polynomial Time [pdf]
  13:45-14:40   I. Oitavem: Monotone recursion versus monotone iteration within FPSPACE 
                (invited talk) [pdf]
  14:40-15:05   U. Dal Lago and P.P. Toldin: A Higher Order Characterization of Probabilistic 
                Polynomial Time [pdf]
  15:05-15:20 Break
  15:20-15:45   Y. Filmus and T. Pitassi: Lower Bounds for Cutting Planes [pdf]
  15:45-16:10   M. Gwynne and O. Kullmann: Attacking DES + AES via SAT: Constraints and 
                boolean functions [pdf]
  16:10-16:35   S. Siebertz and E. Grädel: Dynamic Definability [pdf]
  16:35-17:00   R.J. Lipton and K. Regan: A Finite-Compactness Notion, and Property Testing [pdf]


  • Ulrich Berger (Swansea, Co-Chair)
  • Denis Therien (McGill Montreal, Co-Chair)
  • 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)


  • Michael Benedikt (Oxford, Co-chair)
  • Daniel Leivant (Indiana U, Co-chair)
  • 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)
  • Jean-Yves 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)