DICE is a thematic workshop in the field of Implicit Computational Complexity, where researchers in the area can meet and discuss their most recent results. It takes place annually as part of ETAPS.
Saturday, 2 April 2016, Auditorium 14 (top floor)
| 09:30-10:30 | David Nowak, Formal Security Proofs with Quasi-Interpretations (invited talk) [slides] |
| 10:30-11:00 | coffee break |
| 11:00-11:45 | Alberto Cappai and Ugo Dal Lago: On Equivalences, Metrics, and Polynomial Time [abstract] [slides] [video] |
| 11:45-12:30 | Cynthia Kop: On First-order Cons-free Term Rewriting and PTIME [abstract] [slides] [video] |
| 12:30-14:00 | lunch |
| 14:00-14:45 | Laure Daviaud: Max-Plus Automata for the Worst-Case Complexity Analysis [abstract] [slides] [video] |
| 14:45-15:30 | Jean-Yves Moyen and Jakob Grue Simonsen: More intentional versions of Rice's Theorem [abstract] [slides] [video] |
| 15:30-16:00 | coffee break |
| 16:00-16:45 | Thomas Rubiano and Jean-Yves Moyen: Detection of Non-Size Increasing Programs in Compilers [abstract] [slides] [video] |
| 16:45-17:30 | Beniamino Accattoli and Giulio Guerrieri: Open Call-by-Value [abstract] [slides] [video] |
Sunday, 3 April 2016, Auditorium 14 (top floor)
| 09:30-10:30 | Robin Cockett: Abstract Computability (invited talk) [abstract] [slides] [video] |
| 10:30-11:00 | coffee break |
| 11:00-11:45 | Ezgi Cicek, Marco Gaboardi and Deepak Garg: Cost analysis: How do monads and comonads differ? [abstract] [slides] [video] |
| 11:45-12:30 | Jonas Frey and Jakob Grue Simonsen: Toposes for Time Complexity Classes [abstract] [slides] |
| 12:30-14:00 | lunch |
| 14:00-14:45 | Reinhard Kahle, Isabel Oitavem and Thomas Strahm: An applicative theory for the #P hierarchy FCH [abstract] [slides] [video] |
| 14:45-15:30 | Anupam Das and Patrick Baillot: Towards feasibility in arithmetic via linear logic [abstract] [video] |
| 15:30-16:00 | coffee break |
| 16:00-16:45 | Stéphane Gimenez and Georg Moser: The Complexity of Interaction [asbtract] [slides] [video] |
| 16:45-17:30 | Giulio Guerrieri, Luc Pellissier and Lorenzo Tortora De Falco: Relational type-checking of connected proof-structures [abstract] [slides] [video] |
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 but only in terms of language restrictions or logical/computational principles implying complexity properties.
This workshop focuses on ICC methods related to programs. Traditionally, 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 workshop will be open to contributions on various aspects of ICC including (but not limited to):
Authors are invited to submit an extended abstract of up to 5 pages by February 8, 2016, using the DICE 2016 EasyChair page.
Abstracts must be written in English and be submitted as a single PDF file.
Submissions will be judged on originality, relevance, interest and clarity. Accepted abstracts will be presented at the workshop. Abstracts may contain material already published elsewhere before the workshop. Preference will be given to abstracts containing novel work (including work in progress).
The workshop will not have formal proceedings and is not intended to preclude later publication at another venue.
Submissions of abstracts by PC members are allowed.
This is the 7th edition of DICE. Information about previous instances of the workshop and special issues of journals can be found at the homepage of the DICE workshop series.
