LCC'19 MEETING
The Twenteeth International Workshop on Logic and Computational Complexity
will be held in Patras, Greece, on July 8, 2019, as part of
ICALP
.
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.
IMPORTANT DATES
| Submission deadline: |
May 1, 2019 |
| Authors' notification: |
May 20, 2019 |
| Workshop: |
July 8, 2019 |
INVITED SPEAKERS
-
Daniel Leivant - Title: Finite functions as data objects: A new paradigm for complexity certification
(Indiana University, US)
-
Ramyaa - Title: First order logic with least fixed point operator
(New Mexico Tech, US)
-
Thomas Seiller - Title: Semantics and complexity lower bounds
(CNRS Paris, France)
-
Thomas Zeume - Title: Dynamic Descriptive Complexity of Reachability
(TU Dortmund, Germany)
CONTRIBUTED TALKS
Amirhossein Akbar Tabatabai. Witnessing Games in Generalized Bounded Arithmetic
Raheleh Jalali. Proof Complexity of Focused Calculi Le Thanh Dung Nguyen. Logarithmic space queries and regular transductions in the elementary affine lambda-calculus
Eleni Bakali, Aggeliki Chalki and Aris Pagourtzis.
Descriptive complexity of classes of easy-to-decide counting problems
Arved Friedemann, Jay Morgan.
Using Satisfiability Solvers for Problems in Machine Learning
LCC 2019 PROGRAMME
-
- 1st session
- 09:00 - 09:10
- Opening
- 09:10 - 10:00
- Finite functions as data objects: A new paradigm for complexity certification (invited talk)
Daniel Leivant (Indiana University)
Abstract:
The design of general-purpose imperative programming languages that capture feasible computing, such as polynomial time, is of obvious practical as well as theoretical interest. We obtain such languages by construing finite structures as basic data objects, adopting an imperative programming language for the transformation of such data, using depletion as a generic and abstract representation of recurrence, and finally ramifying the depletion process to block exponential explosions of computation resources. The resulting languages encompass a considerably broader class of algorithms than existing approaches.
- 10:00 - 10:30
- break
- 10:30 - 10:55
-
Witnessing Games in Generalized Bounded Arithmetic
Amirhossein Akbar Tabatabai
- 10:55 - 11:20
-
About a Conway-type result for tree language
Carlos Camino, Volker Diekert, Besik Dundua and Mircea Marin
- 11:20 - 11:40
- break
- 2nd session
- 11:40 - 12:30
- Dynamic Descriptive Complexity of Reachability (invited talk)
Thomas Zeume (TU Dortmund)
Abstract: Dynamic descriptive complexity theory studies how query results can be
updated in a highly parallel fashion, that is, by constant-depth
circuits or, equivalently, by first-order formulae. After gently
introducing dynamic complexity theory, I will discuss recent results
regarding the dynamic complexity of the reachability query.
- 12:35 - 13:00
- Descriptive complexity of classes of easy-to-decide counting problems
Eleni Bakali, Aggeliki Chalki and Aris Pagourtzis
- 13:00 - 14:30
- lunch break
-
- 3rd session
- 14:30 - 15:20
- Semantics and complexity lower bounds
(invited talk)
Thomas Seiller (CNRS Paris)
Abstract:
I have been investigating for some time the question of proving separation and/or lower bounds results using techniques and results from specific models of linear logic I introduced under the name « Interaction Graphs ». Related to game semantics and Girard’s geometry of interaction models, the latter propose a mathematical model of programs and the dynamics of their execution founded upon the proofs-as-programs correspondance.
After sketching the main lines of this work and the questions arising from it, I will focus on a recent result obtained in collaboration with Luc Pellissier. Based on the mathematics at work in Interaction Graphs, we provide an abstract account of three lower bounds results from the literature which were not known to be related. Moreover, this abstraction allows us to refine the most involved of those results — due to Mulmuley (1999) —, improving the state-of-the-art on the P vs NC question.
- 15:20 - 15:45
- Logarithmic space queries and regular transductions in the elementary affine lambda-calculus
Le Thanh Dung Nguyen
- 15:45 - 16:10
- Proof Complexity of Focused Calculis
Raheleh Jalali
- 16:10 - 16:40
- break
-
- 4th session
- 16:40 - 17:30
- First order logic with least fixed point operator (invited talk)
Ramyaa (New Mexico Tech)
Abstract: Fixed point extensions of first order logic have been studied extensively with regards to expressibility. A lot of the work has restricted the models to be finite, but infinite models have been studied as well. Here we explore the deductive power of first order logic extended with least fixed point operator, and finitely axioms stating that the result is the least fixed point.
- 17:30 - 17:55
- Using Satisfiablity Solvers for Problems in Machine Learning
Arved Friedemann, Jay Morgan
- 17:55 - 18:00
- Closing
PROGRAM CHAIRS
PROGRAM COMMITTEE
SUBMISSION OF PAPERS
Submissions must be in English and in the form of an abstract of about 3-4
pages. All submissions should be submitted through Easychair at:
https://easychair.org/conferences/?conf=lcc19
We also welcome submissions of abstracts based on work 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.
REGISTRATION
See ICAPL 2019 registration (Please register asap, early registration ends 9th June.)
CONTACT
To contact the workshop organizers, please send e-mail to
lcc19@easychair.org.
|