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.
|