Developments in Implicit Computational Complexity

Thessaloniki, Greece - April 14-15, 2018 - part of ETAPS 2018

Context

DICE is a thematic workshop in the field of Implicit Computational Complexity (ICC), where researchers in the area can meet and discuss their most recent results. It takes place anually as part of ETAPS.

This edition of the workshop is dedicated to Martin Hofmann, who passed away in January while hicking in Japan.

Scope and Topics

The area of Implicit Computational Complexity (ICC) has grown from several proposals for using logic and formal methods to provide languages for complexity-bounded computation (e.g. PTIME, LOGSPACE computation). Its aim is to study computational complexity without reference to external measuring conditions or particular machine models, but only in terms of language restrictions or logical/computational principles implying complexity properties. This workshop focuses on ICC methods related to programs (rather than descriptive methods). In this approach one relates complexity classes to restrictions on programming paradigms (functional programs, lambda calculi, rewriting systems), such as ramified recurrence, weak polymorphic types, linear logic and linear types, and interpretative measures. The two main objectives of this area are:

Therefore ICC connects both to the study of complexity classes and to static program analysis, in particular, resource analysis. With the aim to more closely bring together researches from these fields, this year contributions related to program’s resource analysis are strongly encouraged.

The workshop is open to contributions on various aspects of ICC and resource analysis, including (but not exclusively):

Invited Speakers

Program

Saturday
08:30 - 9:00 Welcome
09:00 - 10:00 Anupam Das: Monotonicity in logic and complexity (invited talk)
10:00 - 10:30 Coffee Break
10:30 - 11:15 Łukasz Czajka: Term rewriting characterisation of LOGSPACE for finite and infinite data (abstract)
11:15 - 12:00 Michael Schaper: Automated resource analysis with paicc (abstract)
12:00 - 14:30 Lunch Break
14:30 - 15:15 Lê Thành Dũng Nguyễn: On the complexity of finding cycles in proof nets (abstract)
15:15 - 16:00 Florian Steinberg and Eike Neumann: Parametrised second-order complexity theory with applications to the study of interval computation (abstract)
16:00 - 16:30 Coffee Break
16:30 - 17:15 Beniamino Accattoli, Andrea Condoluci and Claudio Sacerdoti Coen: Sharing equality is linear (abstract)
17:15 - 18:00 Miguel Couceiro, Erkko Lehtonen, Pierre Mercuriali, Romain Péchoux and Mathias Soeken: Normal form systems generated by single connectives have mutually equivalent efficiency (abstract)
18:00 - 18:30 Business Meeting
19:30 - — Workshop Dinner at Christofer. The restaurant is reachable from the ETAPS venue by a 15 minute walk along the sea to the south.
Sunday
09:00 - 10:00 Jan Hoffmann: Resource analysis for probabilistic programs (invited talk)
10:00 - 10:30 Coffee Break
10:30 - 11:15 Beniamino Accattoli, Delia Kesner and Stéphane Graham-Lengrand: Multi types, evaluation lengths, and normal forms (abstract)
11:15 - 12:00 Patrick Baillot and Alexis Ghyselen: Combining linear logic and size types for implicit complexity (abstract)
12:00 - 14:30 Lunch Break
14:30 - 15:15 Martin Avanzini, Ugo Dal Lago and Akihisa Yamada: The interpretation method for probabilistic systems (abstract)
15:15 - 16:00 Ugo Dal Lago and Alexis Ghyselen: On linear dependent types and probabilistic termination (abstract)
16:00 - 16:30 Coffee Break
16:30 - 17:15 Luc Pellissier and Thomas Seiller: Entropy and complexity lower bounds (abstract)
17:15 - 18:00 Damiano Mazza: A functorial approach to reductions among decision problems (abstract)

Venue

The workshop will be held in Thessaloniki, Greece, on April 14-15, 2018, see also the corresponding ETAPS page.

Thessaloniki is a Greek port city on the Thermaic Gulf of the Aegean Sea. It was among the biggest and wealthiest city of the Byzantine Empire and is home to numerous notable Byzantine monuments. Thessaloniki features a mild climate, with average temperatures almost 20 degree in the second week of April.

Submission

Authors are invited to submit an extended abstract of up to 5 pages by 7 February, 2018. Abstracts must be written in English and must be prepared using the LaTeX LIPIcs style template of 2016. Submissions are handled via the DICE 2018 EasyChair page.

Submissions will be judged on originality, relevance, interest and clarity. Accepted abstracts will be presented at the workshop, and will be made available through the workshop’s webpage. It is not intended to preclude later publication at another venue. Abstracts can contain material already published elsewhere. Preference will be given to abstracts containing novel work (including work in progress).

Submissions of abstracts by PC members are allowed and encouraged.

Importand Dates

Program Committee

Steering Committee

Registration

Online registration is handled via the ETAPS website.