LCC 2026

16th International Workshop on Logic and Computational Complexity

July 18-19, 2026, Lisbon

as part of the Federated Logic Conference FLoC’26.

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.

Important dates

  • submission May 10, 2026
  • notification May 17, 2026
  • workshop July 18-19, 2026

Invited speakers

  • Olaf Beyersdorff, Friedrich Schiller University Jena
  • Arnold Beckmann, Swansea University
  • Bruno Loff, University of Lisbon

Submission

We welcome submissions of abstracts based on work which may be submitted or published elsewhere, provided that all pertinent information is disclosed at submission time. There will be no formal reviewing as is usually understood in peer-reviewed conferences with published proceedings. The program committee checks relevance and may provide additional feedback.

Submissions must be in English and in the form of an abstract of about 2-4 pages. All submissions should be submitted as a pdf-file via:

https://submissions.floc26.org/lcc/

Program committee

Program

Day 1: Saturday July 18

Saturday morning 1: 09:00 - 10:40 Chair: Isabel Oitavem

  • 09:00-10:00. B. Loff (invited talk): The Switching Lemma shows what the Switching Lemma cannot prove: The natural proofs barrier in constant-depth-circuits
  • 10:00-10:40. V. Holzapfel: Recurrent Arithmetic Circuits

Coffee Break: 10:40 - 11:10

Saturday morning 2: 11:10 - 12:30 Chair: Heribert Vollmer

  • 11:10-11:50. F. Chudigiewitsch, T. Tantau: On the Expressive Power of Modification Problems
  • 11:50-12:30. F. Ferrari, E. Hainry, R. Péchoux, M. Silva: Quantum Programming in Polylogarithmic Time

Lunch: 12:30 - 14:00

Saturday afternoon 1: 14:00 - 15:20 Chair: Isabel Oitavem

  • 14:00-14:40. K. Sauerwald, J. Kontinen, A. Meier: Complexity of Entailment for Cumulative Propositional Dependence Logics
  • 14:40-15:20. L. Strieker: Uniformity in Transformer Models

Coffee Break: 15:20 - 15:50

Saturday afternoon 2: 15:50 - 17:10 Chair: Bruno Loff

  • 15:50-16:30. A. Krapivin, B. Przybocki, B. Subercaseaux: The CNF Encoding Complexity of Boolean Functions and Non-Uniform Computation
  • 16:30-17:10. K. Lange: Approximating the Values of Boolean Formulae in TC0

Day 2: Sunday, July 19

Sunday morning 1: 09:00 - 10:40 Chair: Isabel Oitavem

  • 9:00-10:00. Arnold Beckmann (invited talk): On the Complexity of Confluence and Church-Rosser Proofs, with Applications to Bounded Arithmetic
  • 10:00-10:40. M. D’Adda, G. Vanoni: Towards Higher-Order Logarithmic Space

Coffee Break 10:40 - 11:10

Sunday morning 2: 11:10 - 12:30 Chair: Arnold Beckmann

  • 11:10-11:50. M. Ertel, E. Skapinakis: Characterizing levels of computational complexity by restrictions on hypothetical reasoning
  • 11:50-12:30. J. Murwanashyaka: Notes on Sequential Theories

Lunch: 12:30 - 14:00

Sunday afternoon 1: 14:00 - 15:20 Chair: Heribert Vollmer

  • 14:00-14:40. S. Lukumbuzya, M. Ortiz, M. Simkus: On the Expressive Power of Ontology-Mediated Queries: Capturing coNP
  • 14:40-15:20. M. Bannach, J. Fichte, J. Groven, M. Hecher: Counting Complexity of ASP

Coffee Break: 15:20 - 15:50

Sunday afternoon 2: 15:50 - 17:00 Chair: Heribert Vollmer

  • 15:50-16:50 Olaf Beyersdorff (invited talk): Proof complexity of QBF: relations to circuits and computationally hard problems
  • 16:50-17:00 Closing