Computability in Europe 2023

Unity of Logic and Computation

24-28 July 2023, Batumi, Georgia

About CiE 2023

The event is the 19th 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. The conference will be held in hybrid mode.

Previous meetings have taken place in Amsterdam (2005), Swansea (2006), Siena (2007), Athens (2008), Heidelberg (2009), Ponta Delgada (2010), Sofia (2011), Cambridge (2012), Milan (2013), Budapest (2014), Bucharest (2015), Paris (2016), Turku (2017), Kiel (2018), Durham (2019), Salerno (2020, virtually), Ghent (2021, virtually), and Swansea (2022).

Where

Batumi Shota Rustaveli State University, Rustaveli str. 32, Batumi, Georgia

When

Monday to Friday
24-28 July, 2023

Speakers

Confirmed Tutorial and Plenary Speakers

Ludovic Perret

Ludovic Perret

Sorbonne University, France

Impact of Quantum Computing to Cryptography

Ludovic Levy Patey

Ludovic Levy Patey

Université Paris Diderot, France

Ramsey's theory computes through sparsity

Mark Steedman

Mark Steedman

University of Edinburgh, UK

Inference in the Time of GPT

Andrei Bulatov

Andrei Bulatov

Simon Fraser University, Canada

The Complexity of CSP-Based Ideal Membership Problems

Anne Condon

Anne Condon

The University of British Columbia, Canada

Towards more robust schemes for programming molecules

Neil Lutz

Neil Lutz

Swarthmore College, USA

Applying Algorithmic Dimensions to Classical Problems

Stephanie Dick

Stephanie Dick

Simon Fraser University, Canada

God Has More Disk Space Than We Do

Kirsten Eisenträger

Kirsten Eisenträger

The Pennsylvania State University, USA

Undecidability and undefinability in algebraic extensions of the rationals

Submissions

  • The CiE conferences serve as an interdisciplinary forum for research in all aspects of computability, foundations of computer science, logic, and theoretical computer science, as well as the interplay of these areas with practical issues in computer science and with other disciplines such as biology, mathematics, philosophy, or physics.

  • THE PROGRAM COMMITTEE cordially invites all researchers, European and non-European, to submit their papers in all areas related to the above for presentation at the conference and inclusion in the proceedings of CiE 2023 at EasyChair.

    Papers submitted to the conference proceedings should represent original work, not simultaneously submitted to another journal or conference with formal proceedings. The Program Committee will rigorously review and select submitted papers. Accepted papers will be published as a proceedings volume in the Lecture Notes in Computer Science (LNCS) series from Springer-Verlag.

    Papers to be considered in the conferences proceedings must be submitted in PDF format, using the LNCS style (see Springer conference proceedings guidelines) and must have a maximum of 12 pages, including references but excluding a possible appendix in which one can include proofs and other additional material. Papers building bridges between different parts of the research community are particularly welcome.

  • 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, using the LNCS style (see Springer conference proceedings guidelines), and be 1 page long; 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 2023 may appear or may have appeared in other conferences with formal proceedings and/or in journals.

    • Article submission deadline: February 15, 2023 (AoE)
    • Author notification: April 20, 2023
    • Camera-ready due: May 1, 2023
    • Informal presentations deadline: June 8, 2023 (acceptance notifications will be sent a few days after submission)
    • Early registration deadline: June 18, 2023

Travel Grants

Application for travel grants is overdue.

  • We are happy to announce that within the framework of the Women in Computability program, we are able to offer some grants for junior women researchers who want to participate in CiE 2023. Applications for this grant should be sent to Liesbeth de Mol, liesbeth.de-mol@univ-lille.fr, before May 15, 2023 and include a short cv (at most 2 pages) and contact information for an academic reference. Preference will be given to junior women researchers who are presenting a paper (including informal presentations) at CiE 2023.

  • We are happy to announce that the Association for Symbolic Logic (ASL) is offering Student Travel Awards for ASL members who want to participate in CiE 2023. Applications for this award should be submitted to the ASL office before April 24, 2023. For more details, please consult the Student Travel Awards page or contact Shannon Miller, the ASL administrator, at asl@uconn.edu.

Program

The conference proceedings are officially available since July 18, 2023.

The participants can have free access until August 20, 2023 to the proceedings via the link: https://link.springer.com/book/10.1007/978-3-031-36978-0

    • Merlin Carl. All Melodies are Lost -- Recognizability for weak and strong α-ITRMs
    • Victor Selivanov. Extending Wagner's hierarchy to Deterministic Visibly Pushdown Automata
    • Alexey Milovanov. Some Games on Turing Machines and Power from Random Strings
    • Alexey Barsukov and Florent Madelaine. On guarded extensions of MMSNP
    • Alexander Shen. Inequalities for entropies and dimensions
    • Guohua Wu and Hong Hanh Tran. Cupping computably enumerable degrees simultaneously
    • Zeev Nutov. An O(√k)-approximation algorithm for minimum power k edge disjoint st-paths
    • Ivan Georgiev. Subrecursive Graphs of Representations of Irrational Numbers
    • Russell Miller. A directed system of Scott ideals
    • Lorenzo Galeotti, Ethan Lewis and Benedikt Loewe. Symmetry for transfinite computability
    • Suthee Ruangwises. Physical Zero-Knowledge Proof for Ball Sort Puzzle
    • Daniil Musatov and Georgii Potapov. Structural Complexity of Rational Interactive Proofs
    • Keita Hiroshima and Akitoshi Kawamura. Elementarily traceable irrational numbers
    • Vladislav Orekhovskii and Victor Selivanov. Logic vs topology on regular ω-languages
    • Pablo Arrighi, Amélia Durbec and Pierre Guillon. Graph subshifts
    • Takayuki Kihara and Arno Pauly. The de Groot dual of represented spaces
    • Gabriele Buriola, Peter Schuster and Ingo Blechschmidt. A Constructive Picture of Noetherianity and Well Quasi-Orders.
    • Sam Sanders. The non-normal abyss in Kleene's computability theory
    • Pacôme Perrotin and Sylvain Sené. Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics
    • Vittorio Cipriani and Arno Pauly. The Weihrauch complexity of the supergraph problem
    • Paweł Parys and Aleksander Wiącek. Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games

    • Zhansaya Tleuliyeva. Rogers Semilattice of Limitwise Monotonic Numberings
    • Djamel Eddine Amir and Mathieu Hoyrup. Products do not preserve computable type
    • Juvenal Murwanashyaka. On a First-Order Theory of Building Blocks and its Relation to Arithmetic and Set Theory
    • Konstantinos Papafilippou. An expressively complete tangle operator for the topological μ-calculus
    • Lars Kristiansen. On a Lattice of Degrees of Representations of Irrational Numbers
    • Arno Pauly and Sam Ruggles. The Lebesgue Universal Covering Problem is computable
    • Elvira Mayordomo. A point to set principle for finite-state dimension
    • Giovanni Soldà. A version of the minimax theorem in reverse mathematics
    • Alexander Shekhovtsov and Georgii Zakharov. Kolmogorov Complexity of Infinite Sets
    • Suthee Ruangwises. The Landscape of Computing Symmetric n-Variable Functions with 2n Cards
    • Minha Lee, Soyeon Jeong and Seongbin Park. On hypotheses under which P = NP
    • Gabriel Istrate. Efficient (Propositional) Proofs of Statements in Combinatorial Topology and Related Areas
    • Tomoyuki Yamakami. Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
    • Jiale Chen, Dima Grigoriev and Vladimir Shpilrain. Digital signature schemes using non-square matrices or scrap automorphisms

  • Classical Theories of Degrees (organizers: Keng Meng Ng, Andrea Sorbi)

    • Klaus Ambos-Spies. Multiple Permitting Notions For The Not Totally ω-C.A. Computably Enumerable Degrees
    • Wu Guohua. Simultaneous cupping and continuity in bounded Turing degrees
    • Iskander Kalimullin. Primitive recursive degree spectra of structures
    • Mariya Soskova. The relationship between local and global structure in the enumeration degrees

    Computational Sciences (organizers: Jonathan Gryak, V Anne Smith)

    • Franziska Matthäus. Understanding Collective Phenomena in Multicellular Systems through Agent-based Models
    • Jon Paul Janet. Accelerating Drug Design with AI & Simulation
    • Karianne Bergen. Earthquake monitoring, Deep Learning and Explainable AI
    • Arjen Hommersom. Learning Temporal Bayesian Networks for Understanding Effects of Health Interventions

    Proof Theory (organizers: Anupam Das, Gilda Ferreira)

    • Sam Sanders. Exploring the abyss in Reverse Mathematics and Computability theory
    • Emil Jeřábek. Disjunction-free disjunction property
    • Marie Kerjean. Gödel's Dialectica transformation is reverse differentiation
    • Willem Heijltjes. Willem's Adventures in Curry-Howard Land

    Scalable Computational Genomics (organizers: Giovanna Rosone, Alexandru Tomescu)

    • Camille Marchet. Hashing-based data-structures for querying large k-mer (collections of) sets
    • Jasmijn Baaijens. AmpliVar: an Optimized Amplicon Sequencing Approach to Estimating Lineage Abundances in Viral Metagenomes
    • Erik Garrison. Building and understanding the human pangenome
    • Chirag Jain. Revisiting Graph-theoretic Models for Genome Assembly in the Era of Long Reads

    Weihrauch Complexity (organizers: Damir Dzhafarov, Arno Pauly)

    • Manlio Valenti. Is there a jump in the Weihrauch lattice?
    • Tonicha Crook. Exploring the Non-Computability of Machine Learning Classifiers
    • Vasco Brattka. On the complexity of learning programs
    • Andrej Bauer. Variations on Weihrauch degrees

    • Besik Dundua. PpLog: Logic Programming, Rules, and Strategies
    • Anriette Bishara, Lia Kurtanidze, Mikheil Rukhaia and Lali Tibua. Unranked Probabilistic Logic
    • Temur Kutsia, Mircea Marin and Mikheil Rukhaia. Tolerance-Based Techniques for Approximate Reasoning

  • Times / Days Monday, July 24 Tuesday, July 25 Wednesday, July 26 Thursday, July 27 Friday, July 28
    09:00-09:30 Levy Patey 2 slides Levy Patey 3 slides Bulatov slides Lutz
    09:30-10:00
    10:00-10:30 Levy Patey 1 slides
    10:30-11:00 special sessions
    D: Kalimullin slides / Wu slides
    G: Garrison/Baaijens
    special session
    P: Sanders slides / Kerjean slides
    special sessions
    C: Hommersom/Janet
    W: Valenti slides / Brattka slides
    contributed talks
    11:00-11:30 Perret 1 slides
    11:30-12:00
    12:00-12:30
    12:30-13:00
    13:00-13:30
    13:30-14:00 contributed talks /
    Poster Session
    Perret 2 slides Perret 3 slides Steedman
    14:00-14:30
    14:30-15:00 contributed talks special session
    P: Jeřábek slides /Heijltjes
    contributed talks
    15:00-15:30
    15:30-16:00 special sessions
    D: Soskova / Ambos-Spies slides
    G: Marchet slides / Jain slides
    16:00-16:30 contributed talks special sessions
    C: Matthäus slides / Bergen
    W: Bauer slides / Crook
    16:30-17:00 Eisenträger slides
    17:00-17:30 Condon slides Dick
    17:30-18:00
    18:00-18:30
    18:30-19:00
    19:00-19:30
    19:30-20:00
    20:00-20:30
    20:30-21:00

    Color code tutorial plenary talks special sessions contributed talks
    Special sessions C = computational sciences D = degree theory G = scalable genomics P = proof theory W = Weihrauch degrees

  • Day Time Room 1 Room 2 Room 3
    Monday,
    July 24
    13:30-14:00 Merlin Carl
    All Melodies are Lost -- Recognizability for weak and strong α-ITRMs
    Alexey Milovanov
    Some Games on Turing Machines and Power from Random Strings
    slides
    Suthee Ruangwises
    Physical Zero-Knowledge Proof for Ball Sort Puzzle
    slides
    14:00-14:30 Lorenzo Galeotti, Ethan Lewis and Benedikt Loewe
    Symmetry for transfinite computability
    Djamel Eddine Amir and Mathieu Hoyrup
    Products do not preserve computable type
    Suthee Ruangwises
    The Landscape of Computing Symmetric n-Variable Functions with 2n Cards
    slides
    14:30-15:00 Poster Session
    poster 1 poster 2 poster 3
    Alexander Shen
    Inequalities for entropies and dimensions
    slides
    Jiale Chen, Dima Grigoriev and Vladimir Shpilrain
    Digital signature schemes using non-square matrices or scrap automorphisms
    slides
    Tuesday,
    July 25
    14:30-15:00 Zhansaya Tleuliyeva
    Rogers Semilattice of Limitwise Monotonic Numberings
    slides
    Alexander Shekhovtsov and Georgii Zakharov
    Kolmogorov Complexity of Infinite Sets
    Ivan Georgiev
    Subrecursive Graphs of Representations of Irrational Numbers
    slides
    15:00-15:30 Elvira Mayordomo
    A point to set principle for finite-state dimension
    slides
    Daniil Musatov and Georgii Potapov
    Structural Complexity of Rational Interactive Proofs
    slides
    Pablo Arrighi, Amélia Durbec and Pierre Guillon
    Graph subshifts
    16:00-16:30 Vittorio Cipriani and Arno Pauly
    The Weihrauch complexity of the supergraph problem
    slides
    Paweł Parys and Aleksander Wiącek
    Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games
    slides video
    Victor Selivanov
    Extending Wagner's hierarchy to Deterministic Visibly Pushdown Automata
    slides
    16:30-17:00 Russell Miller
    A directed system of Scott ideals
    slides
    Zeev Nutov
    An O(√k)-approximation algorithm for minimum power k edge disjoint st-paths
    slides
    Alexey Barsukov and Florent Madelaine
    On guarded extensions of MMSNP
    slides
    Friday,
    July 28
    10:30-11:00 Juvenal Murwanashyaka
    On a First-Order Theory of Building Blocks and its Relation to Arithmetic and Set Theory
    slides
    Giovanni Soldà
    A version of the minimax theorem in reverse mathematics
    Gabriel Istrate
    Efficient (Propositional) Proofs of Statements in Combinatorial Topology and Related Areas
    slides
    11:00-11:30 Takayuki Kihara and Arno Pauly
    The de Groot dual of represented spaces
    Keita Hiroshima and Akitoshi Kawamura
    Elementarily traceable irrational numbers
    Tomoyuki Yamakami
    Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
    slides
    11:30-12:00 Arno Pauly and Sam Ruggles
    The Lebesgue Universal Covering Problem is computable
    Gabriele Buriola, Peter Schuster and Ingo Blechschmidt
    A Constructive Picture of Noetherianity and Well Quasi-Orders.
    slides
    Minha Lee, Soyeon Jeong and Seongbin Park
    On hypotheses under which P = NP
    slides
    14:30-15:00 Konstantinos Papafilippou
    An expressively complete tangle operator for the topological μ-calculus
    Sam Sanders
    The non-normal abyss in Kleene's computability theory
    slides
    Vladislav Orekhovskii and Victor Selivanov
    Logic vs topology on regular ω-languages
    15:00-15:30 Lars Kristiansen
    On a Lattice of Degrees of Representations of Irrational Numbers
    slides
    Guohua Wu and Hong Hanh Tran
    Cupping computably enumerable degrees simultaneously
    slides
    Pacôme Perrotin and Sylvain Sené
    Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics
    slides

Committees

    • Gianluca Della Vedova, The University of Milano-Bicocca, Italy
    • Steffen Lempp, University of Wisconsin-Madison, USA

    • Nikolay Bazhenov, Novosibirsk State University, Russia
    • Manuel Bodirsky, TU Dresden, Germany
    • Vasco Brattka, University of the Bundeswehr Munich, Germany
    • Liesbeth De Mol, University of Lille, France
    • Besik Dundua, Kutaisi International University, Georgia
    • Juan Luis Gastaldi, ETH Zurich, Switzerland
    • Thomas Graf, Stony Brook, USA
    • Delaram Kahrobaei, New York University, USA
    • Ekaterina Komendantskaya, Heriot-Watt University, UK
    • Angeliki Koutsoukou-Argyraki, University of Cambridge, UK
    • Florin Manea, The University of Göttingen, Germany
    • Klaus Meer, Brandenburgische Technische Universität Cottbus – Senftenberg, Germany
    • Isabel Oitavem, NOVA University Lisbon, Portugal
    • Roland Omanadze, Tbilisi State University, Georgia
    • Daniel Paulusma, Durham University, UK
    • Elaine Pimentel, University College London, UK
    • Markus Schmid, Humboldt University of Berlin, Germany
    • Shinnosuke Seki, The University of Electro-Communications, Japan
    • Sebastiaan Terwijn, Radboud University Nijmegen, Netherlands
    • Dan Turetsky, Victoria University of Wellington, New Zealand
    • Linda Westrick, The Pennsylvania State University, USA

    • Anzor Beridze, Batumi Shota Rustaveli State University, Georgia
    • Mikheil Donadze, Batumi Shota Rustaveli State University, Georgia
    • Besik Dundua (chair), Kutaisi International University and Institute of Applied Mathematics, Tbilisi State University, Georgia
    • Mikheil Rukhaia (co-chair), Institute of Applied Mathematics, Tbilisi State University, Georgia
    • Lela Turmanidze, Batumi Shota Rustaveli State University, Georgia

    • Giorgi Bakradze, Kutaisi International University, Georgia
    • Nino Bolkvadze, Tbilisi State University, Georgia
    • Tatia Dundua, Tbilisi State University, Georgia
    • Tsotne Mikadze, Kutaisi International University, Georgia
    • Alexander Oniani, Kutaisi International University, Georgia

Venue

Conference venue is located in the Batumi city center. The conference will be held in hybrid mode.

Batumi Shota Rustaveli State University

Rustaveli str. 32, Batumi, Georgia

Hotels

Scam emails warning: with our past experience, sometimes conference participants are receiving emails (sent e.g. from "support@ehotelservices.org" or "ops@travellerpoint.org"), offering the booking of hotel accomodation for conference dates. This is a scam! You will find some unpleasant stories about such companies if you google their name. Be careful - the company name and email can change while the phishing method stays the same.

We do not have arrangements with hotels or agencies other than is listed below and these hotels do not ask credit card information!

Era Palace Hotel

Era Palace Hotel

1 KM from the Venue (10-15 minutes walking)

Special offer

Double/twin room with breakfast - 230 GEL
Triple room with breakfast - 250 GEL
Family room with breakfast - 280 GEL

To reserve a room, please send details to erapalace@gmail.com with subject "CiE 2023 reservation".

Hotel Chao

Hotel Chao

1 KM from the Venue (10-15 minutes walking)

Special offer

Double/twin room with breakfast - 195 GEL
Triple room with breakfast - 235 GEL

To reserve a room, please send details to info@hotelchao.ge with subject "CiE 2023 reservation".

Hilton Batumi

Hilton Batumi

50 Meters from the Venue

We do not have special arrangements for this hotel, but we are listing it here because it is right next to the venue.

There are some other well-known brand hotels in Batumi, like Sheraton, Radisson Blu, Best Western, Wyndham, Le Meridien, etc.

Sponsors

Registration

Please note that the Early registration deadline is June 18, 2023 (included) and the Late registration deadline is July 10, 2023 (included)

Online participation registration deadline is extended to July 20, 2023 (included)

At least one author of accepted paper should register with regular/student fee.

Refund policy:
no refund of online participation fee.
Regular/Student registration is eligible for a refund with a 50 Euro cancellation fee, which includes online participation fee (i.e. person will receive a conference sessions link to attend online).
Refund will be possible for requests received until July 10, 2023 (included).
No refund is possible for requests received after July 10, 2023.

Online Participation
20 EUR

  • Online access link to conference sessions

Student Early/Late
100/150 EUR

  • Onsite Participation
  • Conference Materials
  • Coffee Breaks

Regular Early/Late
200/250 EUR

  • Onsite Participation
  • Conference Materials
  • Coffee Breaks

Social Events Early/Late
100/150 EUR

  • Excursion
  • Conference Dinner
  • This ticket can be bought as an add-on to regular registration, or separately for accompanying persons

Contact Us

Address

Institute of Applied Mathematics, Tbilisi State University
University str. 11, 0186 Tbilisi, Georgia

Phone Number

+995 555 373 216