Logic and Computational Complexity

An International Workshop Series


 

LCC'20 MEETING

The Twenty First International Workshop on Logic and Computational Complexity will be held in Saarbrücken, Germany, on July 6, 2020, as part of LICS/ICALP 2020

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 program will consist of invited lectures as well as contributed papers selected by the Program Committee.

UPDATES

  • June 8, 2020: The tentative program can be found below. Registration of this years' LCC workshop is free. Please register for the workshop on the LICS 2020 registration page.
  • April 22, 2020: We are happy to announce Meghyn Bienvenu and Cynthia Kop as invited speakers.
  • April 16, 2020: The LCC Workshop has been moved to July 6, due to logistical reasons regarding the online version.
  • April 9, 2020:
    • Due to the Covid-19 pandemic LICS/ICALP have been moved online. As co-located event, the LCC workshop will take place as a virtual event as well. Further details will follow.
    • The submission and notification deadlines have been postponed by two weeks.

IMPORTANT DATES

Paper/contribution submission deadline: April 22, 2020 May 6, 2020 (AoE)
Authors' notification: May 13, 2020 May 27, 2020
Workshop: July 6, 2020

INVITED SPEAKERS

PROGRAM CHAIRS

PROGRAM COMMITTEE

LCC 2020 TENTATIVE PROGRAMME (all times in CEST)

Welcome
08:45 - 09:30
Welcome Coffee and Technology check
1st session
09:30 - 09:35
Opening
09:35 - 10:35
Cons-free programs and complexity classes between LOGSPACE and PTIME (invited talk)
Cynthia Cop (Radboud University Nijmegen)

Abstract: "Cons-free" (read-only) functional programming languages offer some perspective on difference between various complexity classes, such as LOGSPACE and PTIME. In many recent discussions, we have considered variations of cons-free programs whose expressiveness may lie strictly between these two classes. This has led to some interesting new questions, and new insights.

This talk discusses ongoing work with Neil Jones, Siddharth Bhaskar and Jakob Simonsen.

10:30 - 10:45
Coffee break
10:45 - 12:15
Adequate structures revisited
Siddharth Bhaskar
Tuple Interpretations for Higher-Order Complexity
Cynthia Kop and Deivid Vale
Dynamic Strategies for TcT
Manuel Schneckenreither
12:15 - 14:00
Lunch break
2nd session
14:00 - 15:00
Ontology-Mediated Query Answering in OWL 2 QL: Succinctness and Complexity Landscapes (invited talk)
Meghyn Bienvenu (CNRS Bordeaux)

Abstract: Recent years have seen an increasing interest in ontology-mediated query answering (OMQA), in which the semantic knowledge provided by an ontology is exploited when querying data. One popular ontology language for OMQA is OWL 2 QL, a W3C-standardized language based upon the DL-Lite description logic. This language has the desirable property that OMQA can be reduced to database query evaluation by means of query rewriting. In this talk, I will consider two fundamental questions about OMQA with OWL 2 QL ontologies: 1) Is it possible to devise query rewriting algorithms that produce polynomial-size rewritings? 2) How does the worst-case complexity of OMQA vary depending on the structure of the ontology-mediated query (OMQ)?

After providing a brief introduction to OMQA, I will propose a classification of OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies, and will present the obtained landscapes, which identify the combined complexity of OMQ answering for each class, and whether all OMQs in the class admit polynomial-size first-order, positive existential and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.

This talk is primarily based upon a JACM'18 paper co-authored with Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, and Michael Zakharyaschev.

15:00 - 15:15
Coffee break
15:15 - 16:45
Choiceless Polynomial Time and Symmetry - Limitations of Definability
Benedikt Pago
A Logical Characterization of Constant-Depth Circuits over the Reals
Timon Barlag and Heribert Vollmer
Game comonads and generalised quantifiers
Adam Ó Conghaile and Anuj Dawar
16:45 - 18:00
Get-together: Bring-your-own-coffee/milk/water/beer/whisky-reception

REGISTRATION

Registration of LCC 2020 is free. Please register on the LICS 2020 registration page in order to receive updates and links for the online program of the workshop.

CONTACT

To contact the workshop organizers, please send e-mail to lcc20@easychair.org.