| Monday, 12. June 2017 | |||
|---|---|---|---|
| 8:30–9:15 | Registration | ||
| 9:15–9:30 | Opening | ||
| 9:30–10:30 | Ramsey’s theorem under a computable perspective Ludovic Patey |
||
| 10:30–11:00 | Coffee | ||
| 11:00–12:30 | Tutorial, part 1: Computability theory, reverse mathematics, and combinatorial principles Denis Hirschfeldt |
||
| 12:30–13:30 | Lunch | ||
| 13:30–14:30 | Dynamic and structural properties of the computably enumerable sets Karen Lange |
||
| 14:30–15:00 | Coffee | ||
| Special sessions | |||
| Room 1 | Room 2 | Room 3 | |
| Computability in analysis, algebra, and geometry 1 | History and philosophy of computing 1 | Cryptography and information theory 1 | |
| 15:00–15:45 | Saugata Basu Complexity in different contexts |
Juliette Kennedy Gödel’s Reception of Turing’s Model of Computability: the Shift of Perception in 1934 |
Ivan Visconti Delayed-Input Cryptographic Protocols |
| 15:45–16:30 | Margarita Korovina Outline of Partial Computability in Computable Topology |
Jan von Plato Rosa Politzer and the beginnings of the theory of computable functions |
Luka Music Garbled Quantum Computation |
| 16:30–16:45 | Break | ||
| Special sessions | |||
| Room 1 | Room 2 | Room 3 | |
| Computability in analysis, algebra, and geometry 2 | History and philosophy of computing 2 | Cryptography and information theory 2 | |
| 16:45–17:30 | Alexander Melnikov Eliminating unbounded search in computable algebra |
Hector Zenil Computability and Causality |
Delaram Kahrobaei Post-quantum Group-Based Cryptography |
| 17:30–18:15 | Russell Miller Computable Transformations of Structures |
Cliff Jones Turing’s 1949 paper in context |
Helger Lipmaa A shuffle argument secure in the generic model |
| Tuesday, 13. June 2017 | |||
|---|---|---|---|
| 9:00–10:00 | The Church-Turing Thesis and Physics Scott Aaronson |
||
| 10:00–10:30 | Coffee | ||
| Contributed session 1 | |||
| Room 1 | Room 2 | Room 3 | |
| 10:30–11:00 | Gleb Novikov Randomness deficiencies |
Hugo Nobrega, Arno Pauly Game characterizations and lower cones in the Weihrauch degrees |
Thierry Monteil A universal oracle for signal machines |
| 11:00–11:30 | Neil Lutz, Donald Stull Dimension Spectra of Lines |
Victor Selivanov Extending Wadge Theory to k-Partitions |
Ville Salo, Ilkka Törmä A One-Dimensional Physically Universal Cellular Automaton |
| 11:30–12:00 | Elvira Mayordomo Effective exact Hausdorff dimension in general metric spaces |
Karoliina Lehtinen, Sandra Quickert $\Sigma^{\mu}_2$ is decidable for $\Pi^{\mu}_2$ |
Martin Delacourt, Nicolas Ollinger Permutive one-way cellular automata and the finiteness problem for automaton groups |
| 12:00–12:30 | Chansu Park, Ji-Won Park, Sewon Park, Dongseong Seon, Martin Ziegler Computable Operations on Compact Subsets of Metric Spaces with Applications to Frechet Distance and Shape Optimization |
Nikolay Bazhenov, Mars Yamaleev Degrees of Categoricity of Rigid Structures |
Pavel Semukhin, Igor Potapov Membership Problem for 2×2 nonsingilar integer matrices |
| 12:30–13:30 | Lunch | ||
| 13:30–15:00 | Tutorial, part 2: Computability theory, reverse mathematics, and combinatorial principles Denis Hirschfeldt |
||
| 15:00–15:30 | Coffee | Women in Computability Workshop | |
| 15:30–16:00 | Juliette Kennedy | ||
| 16:00–16:30 | Karen Lange | ||
| 16:30–17:00 | Ursula Martin | ||
| Break | |||
| 18:00–19:00 | City reception at the Town Hall | ||
| 19:00– | Women in Computability Dinner | ||
| Wednesday, 14. June 2017 | |||
|---|---|---|---|
| 9:00–10:00 | Compressibility and probabilistic proofs Alexander Shen |
||
| 10:00–10:30 | Coffee | ||
| Contributed session 2 | |||
| Room 1 | Room 2 | Room 3 | |
| 10:30–11:00 | Joseph Almog, Vesa Halava Turing completeness, FOL completeness and definability |
Nikolay Bazhenov Turing computable embeddings, computable infinitary equivalence, and linear orders |
Akitoshi Kawamura, Holger Thies, Martin Ziegler Average case complexity for the N-body problem |
| 11:00–11:30 | Patrick Sibelius The Axiom of Choice and Peano Arithmetic do not match |
Karoliina Lehtinen Parity games and the modal mu alternation hierarchy |
Vladimir Aristov, Andrey Stroganov Method of computer analogy: analytics and approximations |
| 11:30–12:00 | Richard Whyman On the Computation and Complexity of Arbitrary Physical Computers |
Luca San Mauro, Ekaterina Fokina, Dino Rossegger Bi-embeddability spectra of structures |
Lorenzo Galeotti, Hugo Nobrega Towards computable analysis on the generalised real line |
| 12:00–12:30 | Vasco Brattka, Rupert Hölzl, Rutger Kuyper Monte Carlo Computability |
Victor Selivanov and Mars Yamaleev Extending a Cooper’s Theorem to $\Delta^0_3$ Turing degrees |
Merlin Carl, Benedikt Löwe, Benjamin Rin Koepke machines and satisfiability for infinitary propositional languages |
| 12:30–13:30 | Lunch | ||
| Break | |||
| 15:00- | Excursion to Herrankukkaro and conference dinner | ||
| Thursday, 15. June 2017 | |||
|---|---|---|---|
| 9:00–10:00 | The computational complexity of query answering under updates Nicole Schweikardt |
||
| 10:00–10:30 | Coffee | ||
| Special sessions | |||
| Room 1 | Room 2 | Room 3 | |
| Algorithmics for biology 1 | Combinatorics and algorithmics on words 1 | Formal languages and automata theory 1 | |
| 10:30–11:15 | Tobias Marschall A Guided Tour to Computational Haplotyping |
Stepan Holub Formalizing a Fragment of Combinatorics on Words |
Kai Salomaa State Complexity of Neighbourhoods of Regular Languages |
| 11:15–12:00 | Fabio Vandin Algorithms for Cancer Mutation Networks |
Pascal Ochem Pattern avoidance |
Martin Kutrib Reversibility in Finite-State Devices |
| 12:00–13:30 | Lunch | ||
| 13:30–15:00 | Tutorial, part 1: Tutorial on Integer Linear Programming in Computational Biology Daniel Gusfield |
||
| 15:00–15:30 | Coffee | ||
| Special sessions | |||
| Room 1 | Room 2 | Room 3 | |
| Algorithmics for biology 2 | Combinatorics and algorithmics on words 2 | Formal languages and automata theory 2 | |
| 15:30–16:15 | Gregory Kucherov Modern algorithmic techniques for biosequence search |
Svetlana Puzynina On variations of Morse and Hedlund theorem |
Thomas Colcombet Hybrid-set-vector automata and gluing of categories |
| 16:15–17:00 | Gianluca Della Vedova Character-based Phylogeny Construction and its Application to Tumor Evolution |
Narad Rampersad Formulas with reversal |
Artur Jez Recompression: new approach to word equations |
| Break | |||
| 17:15–19:00 | General Assembly | ||
| Friday, 16. June 2017 | |||
|---|---|---|---|
| 9:00–10:00 | A Logical Revolution Moshe Vardi |
||
| 10:00–10:30 | Coffee | ||
| Contributed session 3 | |||
| Room 1 | Room 2 | Room 3 | |
| 10:30–11:00 | Robert Barish, Akira Suyama Counting Substrate Cycles in Topologically Restricted Metabolic Networks |
Iosif Petrakis McShane-Whitney pairs |
Merlin Carl, Bruno Durand, Gregory Lafitte, Sabrina Ouazzani Admissibles in gaps |
| 11:00–11:30 | Shilpa Garg and Tobias Moemke A PTAS for Gapless MEC |
Ethan McCarthy Cototal enumeration degrees and the Turing degree spectra of minimal subshifts |
Merlin Carl, Philipp Schlicht The recognizability strength of infinite time Turing machines with ordinal parameters |
| 11:30–12:00 | Stefan Arnold, Jacobo Toran A Deterministic Algorithm for Testing the Equivalence of Read-once Branching Programs with Small Discrepancy |
Kentaro Sato A study on complexity of winning strategy |
Oscar Defrain, Bruno Durand, Gregory Lafitte Infinite time busy beavers |
| 12:00–13:15 | Lunch | ||
| 13:15–14:45 | Tutorial, part 2: Tutorial on Integer Linear Programming in Computational Biology Daniel Gusfield |
||
| 14:45–15:00 | Break | ||
| Contributed session 4 | |||
| Room 1 | Room 2 | Room 3 | |
| 15:00–15:30 | Petr Golovach, Matthew Johnson, Barnaby Martin, Daniel Paulusma, Anthony Stewart Surjective H-Colouring: New Hardness Results |
Lorenzo Carlucci, Leszek Aleksander Kolodziejczyk, Francesco Lepore, Konrad Zdanowski New bounds on the strength of some restrictions of Hindman’s Theorem |
Claus Brillowski A Demonstration of Continuous Name-Binding and Global Information Storage |
| 15:30–16:00 | Daniela Genova, Hendrik Jan Hoogeboom Finite Language Forbidding-Enforcing Systems |
Margarita Korovina, Oleg Kudinov On Higher Effective Descriptive Set Theory |
Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, Mathieu Raffinot Flexible Indexing of Repetitive Collections |
| 16:00–16:30 | Erzsébet Csuhaj-Varjú, György Vaszil Stability Languages of Networks of Watson-Crick D0L Systems |
Alexandra Soskova Structural properties of spectra and $\omega$-spectra |
Manon Stipulanti Generalized Pascal triangles for binomial coefficients of finite words |
| 16:30–17:00 | Coffee | ||