Logic and Computational Complexity

An International Workshop Series


 

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

    Carlos Camino, Volker Diekert, Besik Dundua and Mircea Marin. About a Conway-type result for tree language
    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.