Download Poster

CiE 2018 is the fourteenth conference organized by CiE (Computability in Europe), a European association of mathematicians, logicians, computer scientists, philosophers, physicists and others interested in new developments in computability and their underlying significance for the real world.

Proceedings Survival Guide (PDF)

Association CiE | CiE Conference Series


According to the rules of organising a CiE conference invited and tutorial speakers, speakers at special sessions, Steering Committee members, the PC chairs, special session organizers, and local organizers do not have to pay the registration fee.

If you fall in one of these categories, please send us the registration data by e-mail (First Name, Last Name, Affiliation, and any other special requests you may have, e.g., whether you would like a vegan/vegetarian dinner). These data should be sent at cie2018@email.uni-kiel.de. Please note that if you want to take part to the conference dinner and excursion, this should be booked separately via the registration link.

If you are not one of the aforementioned persons, please register at this link. Special requests, like, e.g., whether you would like a vegan/vegetarian dinner should be send by e-mail at cie2018@email.uni-kiel.de.

Important Dates

  • Extended deadline for abstract submission (abstract submission): January 24, 2018
  • Extended deadline for article submission: February 8, 2018
  • Notification of acceptance: April 6, 2018
  • Deadline for informal presentations submission: May 10, 2018
  • Early registration before: May 30, 2018


Monday, July 30

  Track 1 Track 2 Track 3
8:30 ‐ 9:15

Registration Audimax Lobby

9:15 ‐ 9:30

Opening Frederik-Paulsen-Hörsaal

9:30 ‐ 10:30

Kousha Etessami: Algorithms for some infinite-state stochastic games Frederik-Paulsen-Hörsaal

10:30 ‐ 11:00

Coffee Audimax Lobby

11:00 ‐ 12:00

Tutorial, part 1/3. Bakhadyr Khoussainov: A journey into computably enumerable structures Frederik-Paulsen-Hörsaal

12:00 ‐ 13:30


13:30 ‐ 14:30

Johanna Franklin: Algorithmic randomness in analysis Frederik-Paulsen-Hörsaal

14:30 ‐ 15:00

Coffee Audimax Lobby

  Special sessions
Hörsaal D
Computing with Imperfect Information 1
Hörsaal C
Bioinformatics and Bio-inspired Computing 1
Hörsaal K
Approximation and Optimisation 1
15:00 ‐ 15:45 Ethan McCarthy
Cototal enumeration degrees and the their applications to effective mathematics
Fumiya Okubo
Computing with Multisets: A Survey on Reaction Automata Theory
Kim-Manuel Klein
Using Structural Properties for Integer Programs
15:45 ‐ 16:30 Arno Pauly
Enumeration degrees and topology
Alfonso Paton
Using DNA plasmids as wires for multicellular computing
Asaf Levin
A unified framework for designing EPTAS's for load balancing on parallel machines
16:30 ‐ 16:45


  Special sessions
Hörsaal D
Continuous Computation 1
Hörsaal C
SAT-Solving 1
Hörsaal K
Approximation and Optimisation 2
16:45 ‐ 17:30 Matthew de Brecht
Extending descriptive set theory to non-metrizable spaces and represented spaces
Joao Marques Silva
Computing with SAT Oracles: Past, Present & Future
Sebastian Berndt
Computing Tree Width: From Theory to Practice and Back
17:30 ‐ 18:15 Daniel Graça
Computability of ordinary differential equations
Florian Lonsing
QRAT+: Generalizing QRAT by a More Powerful QBF Redundancy Property
Thomas Erlebach
Computing and Scheduling with Explorable Uncertainty

Tuesday, July 31

  Track 1 Track 2 Track 3
9:00 ‐ 10:00

Mai Gehrke: Can Stone duality be useful in computability? Frederik-Paulsen-Hörsaal

10:00 ‐ 10:30

Coffee Audimax Lobby

  Contributed session 1 parallel: Transfinite Computations (TraC) Workshop
Hörsaal D Hörsaal C Hörsaal K
10:30 ‐ 10:55 Alexander Rybalov
A generic m-reducibility
Florian Steinberg, Arno Pauly, Christine Gassner
Comparing integrability and measurability in different models of computation
Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier
Diminishable Parameterized Problems and Strict Polynomial Kernelization
10:55 ‐ 11:20 Klaus Ambos-Spies
Multiple Permitting and Array Noncomputability
Chansu Park, Sewon Park, Martin Ziegler
On Tensor Calculus in Exact Real Computation: A Case Study from Recursive Analysis to Abstract Data Types
Till Fluschnik, George Mertzios, André Nichterlein
Kernelization Lower Bounds for Finding Constant-Size Subgraphs
11:20 ‐ 11:45 Martin Monath
A c.e. weak truth table degree which is array noncomputable and r-maximal
Franz Brauße, Margarita Korovina, Norbert Müller
Improving Approximations by Taylor Models in Computable Analysis
Paola Bonizzoni, Gianluca Della Vedova, Yuri Pirola, Marco Previtali, Raffaella Rizzi
Divide and Conquer computation of the multi-string BWT and LCP array
11:45 ‐ 12:10 Achilles Beros, Mushfeq Khan, Bjørn Kjos-Hanssen, André Nies
From eventually different functions to pandemic numberings
Svetlana Selivanova, Victor Selivanov
Bit Complexity of Computing Solutions for Symmetric Hyperbolic Systems of PDEs
Alexey Milovanov
Algorithmic Statistics and Prediction for polynomial time-bounded algorithms
12:10 ‐ 13:30


  Contributed session 2
Hörsaal D Hörsaal C Hörsaal K
13:30 ‐ 13:55 Timothy McNicholl, Don Stull
The isometry degree of a computable copy of $\ell^p$
Ivan Georgiev, Lars Kristiansen, Frank Stephan
On General Sum Approximations of Irrational Numbers
Erzsébet Csuhaj-Varjú, Kristóf Kántor, György Vaszil
Languages of P Colony Automata
13:55 ‐ 14:20 Margarita Korovina, Oleg Kudinov
Weak Reduction Principle and Computable Metric Spaces
Marie Nicholson
The complexity of Tukey types and cofinal types
Henning Fernau, Lakshamanan Kuppusamy, Rufus Oladele
New Nonterminal Complexity Results for Semi-Conditional Grammars
14:20 ‐ 14:45 Elvira Mayordomo
A point-to-set principle for separable metric spaces
Satoru Kuroda
On Boolean valued models of Bounded Arithmetic
Florent Becker, Diego Maldonado, Nicolas Ollinger, Guillaume Theyssier
Universality in Freezing Cellular Automata
14:45 ‐ 15:15

Coffee Audimax Lobby

15:15 ‐ 16:15

Tutorial, part 2/3. Bakhadyr Khoussainov: A journey into computably enumerable structures Frederik-Paulsen-Hörsaal

16:30 ‐ 18:00

Women in Computability Workshop. Speakers: Mai Gehrke, Elvira Mayordomo, Monika Seisenberger Hörsaal D

19:00 ‐

Women in Computability dinner

Wednesday, August 1

  Track 1 Track 2 Track 3
9:00 ‐ 10:00

Jeffrey Shallit: Solving Problems in Additive Number Theory with Automata Theory Frederik-Paulsen-Hörsaal

10:00 ‐ 10:30

Coffee Audimax Lobby

  Contributed session 3
Hörsaal D Hörsaal C Hörsaal K
10:30 ‐ 10:55 Michał Tomasz Godziszewski
$\Pi^0_1$-computable quotient presentation of a nonstandard model of arithmetic
Yong Cheng
Two questions about incompleteness
Karoliina Lehtinen
Solving parity games in quasi-polynomial time - a logician's approach
10:55 ‐ 11:20 Nikolay Bazhenov, Margarita Marchuk
Degrees of categoricity for prime and homogeneous models
Merlin Carl
Some Observations on Infinitary Complexity
Stepan Holub
Formalization of Combinatorics on Words in Isabelle/HOL
11:20 ‐ 11:45 Valentina Harizanov
Effective powers of countable structures
Dongseong Seon
Computability of Haar Averages
Lars Kristiansen, Juvenal Murwanashyaka
Decidable and Undecidable Fragments of First-Order Concatenation Theory
11:45 ‐ 12:10 Dag Normann, Sam Sanders
Uniformity in Mathematics
Attila Bagossy, Peter Battyanyi
An encoding of the lambda-calculus into the calculus of String MultiSet Rewriting
Joel Day, Vijay Ganesh, Paul He, Florin Manea, Dirk Nowotka
The Satisfiability of Word Equations: Decidable and Undecidable Theories
12:10 ‐ 13:30


13:30 ‐ 14:30

Tutorial, part 3/3. Bakhadyr Khoussainov: A journey into computably enumerable structures Frederik-Paulsen-Hörsaal

14:30 ‐ 15:00

Best student paper. Dino Rossegger: Elementary bi-embeddability spectra of structures Frederik-Paulsen-Hörsaal

15:00 ‐

Excursion and conference dinner

Thursday, August 2

  Track 1 Track 2 Track 3
9:00 ‐ 10:30

Tutorial, part 1/2. Pinar Heggernes: Enumeration Algorithms Frederik-Paulsen-Hörsaal

10:30 ‐ 11:00

Coffee Audimax Lobby

  Special sessions
Hörsaal D
Computing with Imperfect Information 2
Hörsaal C
Bioinformatics and Bio-inspired Computing 2
History and Philosophy of Computing 1
11:00 ‐ 11:45 Paul Schupp
Asymptotic Density and the Theory of Computability
Bertil Schmidt
Next Generation Sequencing: Big Data meets High Performance Computing
Wilfried Sieg
What is the concept of computation?
11:45 ‐ 12:30 Oliver Kohlbacher
Designing personalized therapies using combinatorial optimization
Paula Quinon
A taxonomy of deviant encodings
12:30 ‐ 13:30


13:30 ‐ 14:30

Alberto Marcone: Looking for ATR_0 in the Weihrauch lattice Frederik-Paulsen-Hörsaal

14:30 ‐ 15:00

Coffee Audimax Lobby

  Special sessions
Hörsaal D
Continuous Computation 2
Hörsaal C
SAT-Solving 2
History and Philosophy of Computing 2
15:00 ‐ 15:45 Mathieu Hoyrup
Topological analysis of representations
Oliver Kullmann
Cube-and-Conquer as a general paradigm for solving SAT and beyond
Christoph Benzmüller
A Deontic Logic Reasoning Infrastructure
15:45 ‐ 16:30 Dag Normann
Functionals of Type 3 as Realisers of Classical Theorems in Analysis
Massimo Lauria
Algorithm analysis through proof complexity
Martin Davis
Turing's Vision and Deep Learning
16:30 ‐ 17:30

History and philosophy of computing reception Senatssitzungssaal Foyer

17:30 ‐ 19:00

General Assembly Frederik-Paulsen-Hörsaal

Friday, August 3

  Track 1 Track 2 Track 3
9:00 ‐ 10:30

Tutorial, part 2/2. Pinar Heggernes: Enumeration Algorithms Frederik-Paulsen-Hörsaal

10:30 ‐ 11:00

Coffee Audimax Lobby

  Contributed session 4
Hörsaal D Hörsaal C Hörsaal K
11:00 ‐ 11:25 Vladimir Uspenskiy, Alexander Shen
Algorithms and Geometric Constructions
Seyyed Alireza Ahmadi
Recurrent Subgroups of Topological Groups
Éric Goubault, Jérémy Ledent, Sergio Rajsbaum
A dynamic epistemic logic semantics for fault-tolerant distributed task computability
11:25 ‐ 11:50 Merlin Carl, Sabrina Ouazzani, Philip Welch
Taming Koepke's Zoo
Pavel Alaev, Victor Selivanov
Polynomial-time Presentations of Algebraic Number Fields
André Souto, Luis Antunes, Andreia Teixeira, Paulo Mateus
Witness hiding without extractors or simulators
11:50 ‐ 12:15 Keith Weber
Generalizations of Infinite Time Turing Machines
Douglas Cenzer, Diego Rojas
Online Computability and Differentiation in the Cantor Space
Ulrich Berger, Olga Petrovska
Optimised program extraction for induction and coinduction
12:15 ‐ 13:30


  Contributed session 5
Hörsaal D Hörsaal C
13:30 ‐ 13:55 Luca San Mauro, Ekaterina Fokina, Dino Rossegger
Measuring the complexity of reductions between equivalence relations
Gualtiero Piccinini, Neal Anderson
Ontic Pancomputationalism

13:55 ‐ 14:20 Nikolay Bazhenov, Manat Mustafa, Mars Yamaleev
On dark Sigma_2^0-equivalence relations
Marta Fiori Carones
The reverse mathematics of a theorem about subgraphs with nice properties

14:30 ‐ 15:30

Alexandra Silva: Decidability and Expressiveness results for Nondeterministic Probabilistic Automata Frederik-Paulsen-Hörsaal

15:30 ‐ 15:45

Closing Frederik-Paulsen-Hörsaal

Previous Conferences


Tutorial Speakers

  • Pinar Heggernes, Bergen, Norway
  • Bakhadyr Khoussainov, Auckland, NZ

Invited Speakers

  • Kousha Etessami, Edinburgh, UK
  • Johanna Franklin, Hempstead, US
  • Mai Gehrke, Paris, France
  • Alberto Marcone, Udine, Italy
  • Alexandra Silva, London, UK
  • Jeffrey O. Shallit, Waterloo, Canada

Special Sessions

  • Approximation and Optimisation
    Organizers: Leah Epstein (Haifa), Klaus Jansen (Kiel)
    Speakers: Sebastian Berndt (Kiel University), Thomas Erlebach (University of Leicester), Kim-Manuel Klein (École Polytechnique Fédérale de Lausanne), Asaf Levin (the Technion, Haifa)
  • Bioinformatics and Bio-inspired Computing
    Organizers: Andre Franke (Kiel), Victor Mitrana (Bucharest)
    Speakers: Oliver Kohlbacher (Universität Tübingen), Alfonso Paton (Universidad Politécnica de Madrid), Bertil Schmidt (Johannes Gutenberg University Mainz), Takashi Yokomori (Waseda University)
  • Computing with Imperfect Information
    Organizers: Timothy McNicholl (Iowa), Mariya Soskova (Wisconsin-Madison)
    Speakers: Eric Astor (University of Connecticut), Ethan McCarthy (University of Wisconsin-Madison), Arno Pauly (Swansea University), Paul Schupp (University of Illinois at Urbana-Champaign)
  • Continuous Computation
    Organizers: Ulrich Berger (Swansea), Dieter Spreen (Siegen)
    Speakers: Matthew de Brecht (Kyoto University), Daniel Graça (University of Algarve), Mathieu Hoyrup (LORIA, Nancy), Dag Normann (University of Oslo)
  • History and Philosophy of Computing
    Organizers: Liesbeth de Mol (Lille), Giuseppe Primiero (Middlesex)
    Speakers: Christoph Benzmüller (Luxembourg/FU Berlin), Martin Davis (New York University), Paula Quinon (Lund University), Wilfried Sieg (Carnegie Mellon University)
  • SAT-Solving
    Organizers: Vijay Ganesh (Waterloo), Olaf Beyersdorff (Leeds)
    Speakers: Oliver Kullmann (Swansea University), Massimo Lauria (Sapienza University Rome), Florian Lonsing (TU Vienna), Joao Marques Silva (University of Lisbon)

Programme Committee

  • Eric Allender, Rutgers
  • Arnold Beckmann, Swansea
  • Marco Benini, Insubria
  • Olaf Beyersdorff, Leeds
  • Patricia Bouyer, Paris
  • Alessandra Carbone, Paris
  • Barbara Csima, Waterloo
  • Anuj Dawar, Cambridge
  • Ekaterina Fokina, Vienna
  • Peter Høyer, Calgary
  • Georgiana Ifrim, Dublin
  • Lila Kari, Waterloo
  • Karen Lange, Wellesley
  • Benedikt Löwe, Amsterdam
  • Barnaby Martin, Durham
  • Florin Manea, Kiel
  • Klaus Meer, Cottbus
  • Russell Miller, New York, co-chair
  • Angelo Montanari, Udine
  • Andrey Morozov, Novosibirsk
  • Anca Muscholl, Bordeaux
  • Dirk Nowotka, Kiel, co-chair
  • Arno Pauly, Bruxelles
  • Giuseppe Primiero, Middlesex
  • Henning Schnoor, Kiel
  • Monika Seisenberger, Swansea
  • Shinnosuke Seki, Tokyo
  • Mariya Soskova, Wisconsin–Madison
  • Peter Van Emde Boas, Amsterdam
  • Heribert Vollmer, Hannover


Organised by

Department of Computer Science, Kiel University

For questions please contact the organisers at the e-mail address cie2018@email.uni-kiel.de.