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
Andrei Bulatov
Simon Fraser University, Canada
The Complexity of CSP-Based Ideal Membership Problems
Anne Condon
The University of British Columbia, Canada
Towards more robust schemes for programming molecules
Kirsten Eisenträger
The Pennsylvania State University, USA
Undecidability and undefinability in algebraic extensions of the rationals
Submissions
-
Conference Topics
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.
-
Paper Submission
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.
-
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, 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.
-
Important Dates
- 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.
-
Women in Computability
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.
-
ASL Student Travel Award
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
-
Accepted Papers
- 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
-
Informal Presentations
- 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
-
Special Sessions
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
-
Poster Session: Logic and Computability in Georgia
- 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
-
Tentative Schedule
Times / Days Monday, July 24 Tuesday, July 25 Wednesday, July 26 Thursday, July 27 Friday, July 28 09:00-09:30 registration/coffee Levy Patey 2 slides Levy Patey 3 slides Bulatov slides Lutz 09:30-10:00 opening 10:00-10:30 Levy Patey 1 slides coffee break Barry Cooper prize announcement / coffee break coffee break coffee break 10:30-11:00 special sessions
D: Kalimullin slides / Wu slides
G: Garrison/Baaijensspecial session
P: Sanders slides / Kerjean slidesspecial sessions
C: Hommersom/Janet
W: Valenti slides / Brattka slidescontributed talks 11:00-11:30 Perret 1 slides 11:30-12:00 12:00-12:30 lunch lunch lunch lunch lunch 12:30-13:00 13:00-13:30 13:30-14:00 contributed talks /
Poster SessionPerret 2 slides Perret 3 slides Steedman 14:00-14:30 excursion to Batumi botanical garden and Makhuntseti waterfall 14:30-15:00 contributed talks special session
P: Jeřábek slides /Heijltjescontributed talks 15:00-15:30 coffee break 15:30-16:00 special sessions
D: Soskova / Ambos-Spies slides
G: Marchet slides / Jain slidescoffee break coffee break 16:00-16:30 contributed talks coffee break special sessions
C: Matthäus slides / Bergen
W: Bauer slides / Crook16:30-17:00 Eisenträger slides 17:00-17:30 Condon slides Dick 17:30-18:00 ACiE closing 18:00-18:30 Welcome Party WiC 18:30-19:00 19:00-19:30 Dinner 19:30-20:00 20:00-20:30 20:30-21:00 Color code tutorial plenary talks special sessions contributed talks social/administrative Special sessions C = computational sciences D = degree theory G = scalable genomics P = proof theory W = Weihrauch degrees -
Contributed Talk Schedule
Day Time Room 1 Room 2 Room 3 Monday,
July 2413:30-14:00 Merlin Carl
All Melodies are Lost -- Recognizability for weak and strong α-ITRMsAlexey Milovanov
Some Games on Turing Machines and Power from Random Strings
slidesSuthee Ruangwises
Physical Zero-Knowledge Proof for Ball Sort Puzzle
slides14:00-14:30 Lorenzo Galeotti, Ethan Lewis and Benedikt Loewe
Symmetry for transfinite computabilityDjamel Eddine Amir and Mathieu Hoyrup
Products do not preserve computable typeSuthee Ruangwises
The Landscape of Computing Symmetric n-Variable Functions with 2n Cards
slides14:30-15:00 Poster Session
poster 1 poster 2 poster 3Alexander Shen
Inequalities for entropies and dimensions
slidesJiale Chen, Dima Grigoriev and Vladimir Shpilrain
Digital signature schemes using non-square matrices or scrap automorphisms
slidesTuesday,
July 2514:30-15:00 Zhansaya Tleuliyeva
Rogers Semilattice of Limitwise Monotonic Numberings
slidesAlexander Shekhovtsov and Georgii Zakharov
Kolmogorov Complexity of Infinite SetsIvan Georgiev
Subrecursive Graphs of Representations of Irrational Numbers
slides15:00-15:30 Elvira Mayordomo
A point to set principle for finite-state dimension
slidesDaniil Musatov and Georgii Potapov
Structural Complexity of Rational Interactive Proofs
slidesPablo Arrighi, Amélia Durbec and Pierre Guillon
Graph subshifts16:00-16:30 Vittorio Cipriani and Arno Pauly
The Weihrauch complexity of the supergraph problem
slidesPaweł Parys and Aleksander Wiącek
Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games
slides videoVictor Selivanov
Extending Wagner's hierarchy to Deterministic Visibly Pushdown Automata
slides16:30-17:00 Russell Miller
A directed system of Scott ideals
slidesZeev Nutov
An O(√k)-approximation algorithm for minimum power k edge disjoint st-paths
slidesAlexey Barsukov and Florent Madelaine
On guarded extensions of MMSNP
slidesFriday,
July 2810:30-11:00 Juvenal Murwanashyaka
On a First-Order Theory of Building Blocks and its Relation to Arithmetic and Set Theory
slidesGiovanni Soldà
A version of the minimax theorem in reverse mathematicsGabriel Istrate
Efficient (Propositional) Proofs of Statements in Combinatorial Topology and Related Areas
slides11:00-11:30 Takayuki Kihara and Arno Pauly
The de Groot dual of represented spacesKeita Hiroshima and Akitoshi Kawamura
Elementarily traceable irrational numbersTomoyuki Yamakami
Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
slides11:30-12:00 Arno Pauly and Sam Ruggles
The Lebesgue Universal Covering Problem is computableGabriele Buriola, Peter Schuster and Ingo Blechschmidt
A Constructive Picture of Noetherianity and Well Quasi-Orders.
slidesMinha Lee, Soyeon Jeong and Seongbin Park
On hypotheses under which P = NP
slides14:30-15:00 Konstantinos Papafilippou
An expressively complete tangle operator for the topological μ-calculusSam Sanders
The non-normal abyss in Kleene's computability theory
slidesVladislav Orekhovskii and Victor Selivanov
Logic vs topology on regular ω-languages15:00-15:30 Lars Kristiansen
On a Lattice of Degrees of Representations of Irrational Numbers
slidesGuohua Wu and Hong Hanh Tran
Cupping computably enumerable degrees simultaneously
slidesPacôme Perrotin and Sylvain Sené
Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics
slides
Committees
-
PC Chairs
- Gianluca Della Vedova, The University of Milano-Bicocca, Italy
- Steffen Lempp, University of Wisconsin-Madison, USA
-
Program Committee
- 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
-
Organizing Committee
- 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
-
Student Volunteers
- 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
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
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
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.
Gallery
Some pictures from excursion
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.
Contact Us
Address
Institute of Applied Mathematics, Tbilisi State UniversityUniversity str. 11, 0186 Tbilisi, Georgia