FELIPE CUCKER
INVITED SPEAKER
Home
Computability in Europe 2019
15th – 19th JULY 2019, DURHAM
COMPUTABILITY IN EUROPE 2019
Computing with Foresight and Industry
#CiE2019
CiE 2019 is the fifteenth 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.
Immediately after CiE 2019 there will be a two-day Workshop on Computability Theory to be held in Leeds on 22-23 July. More information can be found here.
Please download and display our poster.
Programme Committee
- Erika Ábrahám, RWTH Aachen
- Merlin Carl, University of Konstanz
- Erzsébet Csuhaj-Varjú, Eötvös Loránd University
- Walter Dean, University of Warwick
- Gianluca Della Vedova, University of Milano-Bicocca
- Liesbeth De Mol, University of Lille
- Valeria de Paiva, Nuance Communications
- Alessandra Di Pierro, University of Verona
- Henning Fernau, University of Trier
- Johanna Franklin, Hofstra University
- Pawel Gawrychowski, University of Wrocław
- Pinar Heggernes, University of Bergen
- Mathieu Hoyrup, LORIA
- Peter Jonsson, Linköping University
- Dietrich Kuske, TU Ilmenau
- Stephane Le Roux, TU Darmstadt
- Benedikt Löwe, University of Amsterdam
- Florin Manea, Christian-Albrechts-University
- Barnaby Martin, Durham University
- Elvira Mayordomo, University of Zaragoza
- Klaus Meer, BTU Cottbus-Senftenberg
- Dirk Nowotka, Christian-Albrechts-University
- Arno Pauly, Swansea University
- Daniel Paulusma, Durham University (co-chair)
- Daniela Petrisan, Paris Diderot University
- Giuseppe Primiero, University of Milan (co-chair)
- Christine Tasson, Paris Diderot University
- Hélène Touzet, University of Lille
- Peter Van Emde Boas, University of Amsterdam
- Georg Zetzsche, Max Planck Institute
ACCEPTED PAPERS
Nikolay Bazhenov, Manat Mustafa and Sergey Ospichev. Bounded reducibility for computable numberings.
Iskander Kalimullin, Russell Miller and Hans Schoutens. Degree Spectra for Transcendence in Fields.
Xizhong Zheng and Klaus Ambos-Spies. On the Differences and Sums of Strongly Computably Enumerable Real Numbers.
Nikolay Bazhenov, Hristo Ganchev and Stefan Vatev. Effective embeddings for pairs of structures.
Julien Cervelle and Patrick Cegielski. Study of step-wise simulation between ASMs.
Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer, Alexandra Soskova and Stefan Vatev. Cohesive Powers of Linear Orders.
Mate Szabo. Kalmár’s Argument for the Independence of Computer Science.
Paul Bell and Igor Potapov. Towards Uniform Online Spherical Tessellations.
Laurent Beaudou, Florent Foucaud, Florent Madelaine, Lhouari Nourine and Gaétan Richard. Complexity of regular path query homomorphisms.
Jean-Yves Moyen and Jakob Grue Simonsen. More Intensional Versions of Rice’s Theorem.
Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag and Frank Sommer. Destroying Bicolored P3P3s by Deleting Few Edges.
Florian Bridoux, Richard Adrien, Kévin Perrot and Nicolas Durbec. Complexity and Fixed Points in Boolean Networks.
Jiri Wiedermann and Jan van Leeuwen. Finite State Machines with Feedback: An Architecture Supporting Minimal Machine Consciousness.
Lorenzo Carlucci, Leonardo Mainardi and Michael Rathjen. A note on the ordinal of RCA0+WO(σ)RCA0+WO(σ).
Shaoyi Wang, Guohua Wu and Mars Yamaleev. The d.r.e wtt-degrees are dense.
Sam Sanders. Nets and Reverse Mathematics: initial results.
Iosif Petrakis. Borel and Baire sets in Bishop spaces.
Michał Wrocławski. Representations of natural numbers and computability of various functions.
Bruno Durand and Gregory Lafitte. An algorithmic approach to characterizations of admissibles.
Daniil Musatov and Ruslan Ishkuvatov. On approximate uncomputability of the Kolmogorov complexity function.
INFORMAL PRESENTATIONS
Andrew Aberdein. Phylomemetics of a Mathematical Folk Tale.
Péter Battyányi. Feasibility in Nonstandard Heyting Arithmetic.
Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson and Daniël Paulusma. Graph Isomorphism for (H1,H2)-free Graphs: An Almost Complete Dichotomy.
Paola Bonizzoni, Clelia De Felice, Rocco Zaccagnino and Rosalba Zizza. Inverse Lyndon words and Inverse Lyndon factorizations of words.
Vasco Brattka and Guido Gherardi. Weihrauch goes Brouwerian.
Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea and Markus L. Schmid. Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number.
Nicholas Chancellor. Novel Ways of Using Quantum Annealing.
Laura Crosilla. Poincaré, Weyl and a predicative concept of set.
Marta Fiori Carones. Reverse mathematics of a theorem about posets of finite width.
Michael Stephen Fiske. Quantum Random Self-Modifiable Computation.
Zvonko Iljazović. Computable type of certain polyhedra.
Florian Kammueller. Formalizing Probabilistic Quantum Security Protocols in the Isabelle Infrastructure Framework.
Viv Kendon. Continuous-time quantum computing.
Hyunwoo Lee, Sewon Park and Martin Ziegler. Is Brownian Motion Computable?
Luca San Mauro . Punctual equivalence relations and their punctual complexity.
Arno Pauly, Linda Westrick and Liang Yu. Luzin’s (N) and randomness reflection.
Arno Pauly and Zhifeng Matthew Ye. First steps towards computable frame theory.
András Pongrácz. Push and pull protocols on finite graphs.
Dino Rossegger, Luca San Mauro and Meng Che Ho. The complexity of non-trivial homomorphisms between torsion-free abelian groups.
Charles Semple. Looking for trees in phylogenetic networks.
Manlio Valenti. The open and clopen Ramsey theorems in the Weihrauch lattice.
Keita Yokoyama. Finitary infinite pigeonhole principle and Ramsey’s theorem in reverse mathematics.
INVITED AND TUTORIAL SPEAKERS
PROGRAMME
The conference begins at 9am on 15 July and finishes at 3pm on 19 July. Here is the schedule, informal proceedings and LNCS proceedings.
All talks, refreshments and lunches are in the Department of Computer Science in the connected Christopher and Higginson Buildings. Plenary talks are in E005 which is at the front of the Christopher Building (the building faces north), next to the main entrance to the department. A reception desk will be located outside the lecture theatre from 8am on Monday 15 July. Some other talks are in E240 and E360 in the Higginson Building towards the back of the department. Lunches and refreshments are in the Atrium adjacent to E240.
Invited Speakers and Tutorials
Felipe Cucker Computing the Homology of Semialgebraic Sets
Markus Holzer Non-recursive Trade-Offs Are Almost Everywhere
Assia Mahboubi Machine Checked Mathematics
Ursula Martin Journeys in Mathematical Landscapes: Genius or Craft?
Sonja Smets Logic and Computation of Social Behaviour
Linda Brown Westrick Climbing the Hierarchy of Completely Positive Entropy in Two-Dimensional Shifts of Finite Type
Special Sessions
- Probabilistic Programming and Higher-Order Computation (Monday 15 July)
Organizer: Christine Tasson (Paris Diderot University)
Thomas Ehrhard (IRIF, Paris Diderot University) Stability in a Probabilistic Setting
Cameron Freer (MIT) Computable Representations of Exchangeable Data
Joost-Pieter Katoen (RWTH Aachen) Quantitative Separation Logic
Sam Staton (University of Oxford) Semantic Models of Probability with Higher Order Functions - Transfinite Computations (Monday 15 July)
Organizer: Sabrina Ouazzani (LIX, École Polytechnique)
Merlin Carl (University of Konstanz) Ordinal Regularity
Lorenzo Galeotti (University of Hamburg) Surreal Blum-Shub-Smale Machines
Philip Welch (University of Bristol) Higher Type Recursion for Transfinite Machine Theory
Benjamin Rin (Utrecht University) New Directions in Transfinite Complexity - Women in Computability Workshop (Tuesday 16 July)
Organizer: Liesbeth de Mol (Université de Lille)
Erika Ábrahám (RWTH Aachen University)
Ursula Martin (University of Oxford)
Sara Uckelman (Durham University)
There is further information available on the Women in Computability Workshop - History and Philosophy of Computing (Wednesday 17 July)
Organizer: Council of the HaPoC Commission
Tony Hoare (University of Cambridge) Applied Logic and Programming Languages
Michael Jackson (Open University) The Right-Hand Side Problem in Cyber-Physical Systems
Ray Turner (University of Essex) Correctness, Explanation and Intention - Smoothed and Probabilistic Analysis of Algorithms (Wednesday 17 July)
Organizer: Bodo Manthey (University of Twente)
Stefan Klootwijk (University of Twente) Probabilistic Analysis of Facility Location on Random Shortest Path Metrics
Sophie Huiberts (CWI, Amsterdam) A Friendly Smoothed Analysis of the Simplex Method
Clemens Rösner (University of Bonn) The Smoothed Number of Pareto-optimal Solutions in Non-integer Bicriteria Optimization
Sebastian Wild (University of Waterloo) Dual-Pivot Quicksort and Beyond: An Analysis-of-Algorithms Perspective on Multiway Quicksort - Computational Neuroscience (Friday 19 July)
Organizers: Noura Al Moubayed (Durham University) and Jason Connolly (Durham University)
Ulrik Beierholm (Durham University) Learning to Perceive and Act in a Stochastic Environment
Netta Cohen (Leeds University) Sensory Computation in C. elegans
Evelyne Sernagor (Newcastle University) Multielectrode-Array Applications to Investigate Retinal Function in Health and Disease
V Anne Smith (University of St Andrews) Brains and Bayes Nets: Inferring Neural Information Flow - Lowness Notions in Computability (Friday 19 July)
Organizers: Johanna Franklin (Hofstra University) and Joseph S. Miller (University of Wisconsin-Madison)
Kenshi Miyabe (Meiji University) Uniform Relativization
Benoît Monin (LACL, Créteil University) Lowness of the Pigeonhole Principle
Keng Meng Selwyn Ng (Nanyang Technological University) The Computational Strength of Points in Function Spaces
Don Stull (LORIA) Effective Dimension of Planar Lines and Fractal Geometry
There will also be tutorials, contributed talks and informal presentations.
SUBMISSION GUIDELINES
Regular Papers
Regular papers must be submitted via EasyChair and must use the LNCS style file available here. Papers can have a maximum of 12 pages including references, but excluding a possible appendix containing proofs and other additional material. Papers building bridges between different parts of the research community are particularly welcome.
The conference proceedings will be published by Springer in the series Lecture Notes in Computer Science.
Informal Presentations
Continuing the tradition of past CiE conferences, we invite researchers to present informal presentations of their recent work. A proposal for an informal presentation must be submitted via EasyChair and must use the LNCS style file available here and be 1 page; a brief description of the results suffices and an abstract is not required. Informal presentations will not be published in the LNCS conference proceedings. Results presented as informal presentations at CiE 2019 may appear or may have appeared in other conferences with formal proceedings and/or in journals.
IMPORTANT DATES
- Paper Submission: 21st January 2019 AOE
(please note that the deadline has been extended and it is not necessary to submit an abstract in advance of the paper) - Notification: 18th March 2019
- Final Version: 4th April 2019
- Informal Presentations: 1st May 2019
- Notification for Informal Presentations: within a few days of submission
- Early Registration: 17th May 2019
- Final Registration: 25th June 2019
Scam Alert: We are aware that invited speakers and delegates may be contacted by individuals claiming to be affiliated with CiE2019 and offering assistance with accommodation bookings. Please be aware that this is a scam operated by a company calling themselves Business Travel Management. You will never receive any unsolicited contact from the organizers of CiE promoting accommodation.
SPONSORS
 |  |  |  |  |  |
 |  |  |  |
The HaPoc Council offers two HaPoC travel grants of 250USD each to support participation in the conference. To be eligible for a grant, an accepted paper or informal presentation in the area of history and/or philosophy of computing is required. Applications for these grants must be made to HaPoC directly, see hapoc.org/node/284 for further details.
ASL Travel Grants: students, who are members of the Association for Symbolic Logic, may apply for (limited) ASL travel funds that the ASL is making available for sponsored meetings. See aslonline.org/meetings/student-travel-awards/.
There are also Women in Computability Travel Grants available.
DURHAM
The conference is hosted by Algorithms and Complexity in Durham (ACiD), a research group in the Department of Computer Science.
Organizing Committee
- Matthew Johnson (Durham)
- Barnaby Martin (Durham)
- Daniel Paulusma (Durham)
- Giuseppe Primiero (Milan).
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
- CiE 2018: Sailing Routes in the World of Computation, Kiel, Germany
REGISTRATION
Registration is now closed. Regular registration fees are £200 (£250 after 17th May 2019) and student registration fees are £100 (£150 after 17th May 2019). During the conference, registered participants will have free access to the online version of the LNCS conference proceedings on SpringerLink. A discount of £25 will be offered to participants who do not wish to receive a hard copy of the LNCS conference proceedings.