LCC — PROGRAM

Days: Saturday, 18 July 2026 Sunday, 19 July 2026

Saturday, 18 July 2026
09:00-10:40 Saturday morning 1 LCC
Session Chair:
Isabel Oitavem
Location: C4.06
09:00-10:00
The Switching Lemma shows what the Switching Lemma cannot prove: The natural proofs barrier in constant-depth-circuits (abstract) 60 min
Bruno Loff1
1 Lisbon
10:00-10:40
Recurrent Arithmetic Circuits (abstract) 40 min
Vivian Holzapfel1
1 Leibniz Universität Hannover
10:40-11:10 Coffee Break LCC
Location: C4.06
11:10-12:30 Saturday morning 2 LCC
Session Chair:
Heribert Vollmer
Location: C4.06
11:10-11:50
On the Expressive Power of Modification Problems (abstract) 40 min
Florian Chudigiewitsch1, Till Tantau1
1 Universität zu Lübeck
11:50-12:30
Quantum Programming in Polylogarithmic Time (abstract) 40 min
Florent Ferrari1, Emmanuel Hainry2, Romain Péchoux2, Mário Silva3
1 ENS Lyon, France
2 Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
3 Laboratoire Méthodes Formelles, Université Paris-Saclay, Inria
12:30-14:00 Lunch LCC
Location: C4.06
14:00-15:20 Saturday afternoon 1 LCC
Session Chair:
Isabel Oitavem
Location: C4.06
14:00-14:40
Complexity of Entailment for Cumulative Propositional Dependence Logics (abstract) 40 min
Kai Sauerwald1, Juha Kontinen2, Arne Meier3
1 FernUniversität in Hagen
2 University of Helsinki
3 Leibniz Universität Hannover
14:40-15:20
Uniformity in Transformer Models (abstract) 40 min
Laura Strieker1
1 Leibniz Universität Hannover
15:20-15:50 Coffee Break LCC
Location: C4.06
15:50-17:10 Saturday afternoon 2 LCC
Session Chair:
Bruno Loff
Location: C4.06
15:50-16:30
The CNF Encoding Complexity of Boolean Functions and Non-Uniform Computation (abstract) 40 min
Andrew Krapivin1, Benjamin Przybocki1, Bernardo Subercaseaux1
1 Carnegie Mellon University
16:30-17:10
Approximating the Values of Boolean Formulae in TC0 (abstract) 40 min
Klaus-Jörn Lange1
1 Universität Tübingen
Sunday, 19 July 2026
09:00-10:40 Sunday morning 1 LCC
Session Chair:
Isabel Oitavem
Location: C4.06
09:00-10:00
On the Complexity of Confluence and Church-Rosser Proofs, with Applications to Bounded Arithmetic (abstract) 60 min
Arnold Beckmann1
1 Swansea
10:00-10:40
Towards Higher-Order Logarithmic Space (abstract) 40 min
Martino D'Adda1, Gabriele Vanoni2
1 Università di Milano
2 Université Paris Cité
10:40-11:10 Coffee Break LCC
Location: C4.06
11:10-12:30 Sunday morning 2 LCC
Session Chair:
Arnold Beckmann
Location: C4.06
11:10-11:50
Characterizing levels of computational complexity by restrictions on hypothetical reasoning (abstract) 40 min
Marcel Ertel1, Eduardo Skapinakis2
1 Universität Tübingen
2 NOVA University of Lisbon
11:50-12:30
Notes on Sequential Theories (abstract) 40 min
Juvenal Murwanashyaka1
1 None
12:30-14:00 Lunch LCC
Location: C4.06
14:00-15:20 Sunday afternoon 1 LCC
Session Chair:
Heribert Vollmer
Location: C4.06
14:00-14:40
On the Expressive Power of Ontology-Mediated Queries: Capturing coNP (abstract) 40 min
Sanja Lukumbuzya1, Magdalena Ortiz1, Mantas Simkus1
1 TU Wien
14:40-15:20
Counting Complexity of ASP (abstract) 40 min
Max Bannach1, Johannes Klaus Fichte2, Johanna Groven2, Markus Hecher3
1 European Space Agency
2 Linköping University
3 CNRS, CRIL
15:20-15:50 Coffee Break LCC
Location: C4.06
15:50-17:00 Sunday afternoon 2 LCC
Session Chair:
Heribert Vollmer
Location: C4.06
15:50-16:50
Proof complexity of QBF: relations to circuits and computationally hard problems (abstract) 60 min
Olaf Beyersdorff1
1 Jena
16:50-17:00
Closing (abstract) 10 min
Isabel Oitavem1, Vollmer Heribert2
1 Lisbon
2 Hannover
Designed and Developed by EventKey | Copyright 2026 EventKey Last updated:
🔍 ↑