About
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.
Registration
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
Tentative Schedule
Monday, July 30
| Track 1 | Track 2 | Track 3 | |
| 8:30 ‐ 9:15 | Registration | ||
| 9:15 ‐ 9:30 | Opening | ||
| 9:30 ‐ 10:30 | Kousha Etessami: Algorithms for some infinite-state stochastic games | ||
| 10:30 ‐ 11:00 | Coffee | ||
| 11:00 ‐ 12:00 | Tutorial, part 1/3. Bakhadyr Khoussainov: A journey into computably enumerable structures | ||
| 12:00 ‐ 13:30 | Lunch | ||
| 13:30 ‐ 14:30 | Johanna Franklin: Algorithmic randomness in analysis | ||
| 14:30 ‐ 15:00 | Coffee | ||
| Special sessions | |||
| Computing with Imperfect Information 1 | Bioinformatics and Bio-inspired Computing 1 | 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 | Break | ||
| Special sessions | |||
| Continuous Computation 1 | SAT-Solving 1 | 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? | ||
| 10:00 ‐ 10:30 | Coffee | ||
| Contributed session 1 | parallel: Transfinite Computations (TraC) Workshop | ||
| 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 | Lunch | ||
| Contributed session 2 | |||
| 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 | ||
| 15:15 ‐ 16:15 | Tutorial, part 2/3. Bakhadyr Khoussainov: A journey into computably enumerable structures | ||
| 16:30 ‐ 18:00 | Women in Computability Workshop. Speakers: Mai Gehrke, Elvira Mayordomo, Monika Seisenberger | ||
| 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 | ||
| 10:00 ‐ 10:30 | Coffee | ||
| Contributed session 3 | |||
| 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 | Lunch | ||
| 13:30 ‐ 14:30 | Tutorial, part 3/3. Bakhadyr Khoussainov: A journey into computably enumerable structures | ||
| 14:30 ‐ 15:00 | Best student paper. Dino Rossegger: Elementary bi-embeddability spectra of structures | ||
| 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 | ||
| 10:30 ‐ 11:00 | Coffee | ||
| Special sessions | |||
| Computing with Imperfect Information 2 | 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 | Lunch | ||
| 13:30 ‐ 14:30 | Alberto Marcone: Looking for ATR_0 in the Weihrauch lattice | ||
| 14:30 ‐ 15:00 | Coffee | ||
| Special sessions | |||
| Continuous Computation 2 | 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 | ||
| 17:30 ‐ 19:00 | General Assembly | ||
Friday, August 3
| Track 1 | Track 2 | Track 3 | |
| 9:00 ‐ 10:30 | Tutorial, part 2/2. Pinar Heggernes: Enumeration Algorithms | ||
| 10:30 ‐ 11:00 | Coffee | ||
| Contributed session 4 | |||
| 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 | Lunch | ||
| Contributed session 5 | |||
| 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 | ||
| 15:30 ‐ 15:45 | Closing | ||
Previous Conferences
- CiE 2005: New Computational Paradigms, Amsterdam, Netherlands
- CiE 2006: Logical Approaches to Computational Barriers, Swansea, UK
- CiE 2007: Computation and Logic in the Real World, Sienna, Italy
- CiE 2008: Logic and Theory of Algorithms, Athens, Greece
- CiE 2009: Mathematical Theory and Computational Practice, Heidelberg, Germany
- CiE 2010: Programs, Proofs, Processes, Ponta Delgada (Azores), Portugal
- CiE 2011: Models of Computation in Context, Sofia, Bulgaria
- CiE 2012 – Turing Centenary Conference: How the World Computes, Cambridge, UK
- CiE 2013: The Nature of Computation – Logic, Algorithms, Application, Milan, Italy
- CiE 2014: Language, Life, Limits, Budapest, Hungary
- CiE 2015: Evolving Computability, Bucharest, Romania
- CiE 2016: Pursuit of the Universal, Paris, France
- CiE 2017: Unveiling Dynamics and Complexity, Turku, Finland
Speakers
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: Tim 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
Partners
Organised by
Department of Computer Science, Kiel University
For questions please contact the organisers at the e-mail address cie2018@email.uni-kiel.de.