Algorithmic complexity of structural equivalence relations

This is the project page of the project ACOSE - Algorithmic complexity of structural equivalence relations funded by a Marie Skłodowska Curie Global Fellowship under Horizon 2020 of the European Commission.

The goal of this project is to investigate the relationship between notions of complexity in computable structure theory and notions of complexity in descriptive set theory. The project consist of a two year outgoing phase at the University of California, Berkeley and a one year return phase at Technische Universität Wien.

Participants

• Principal Investigator: Dino Rossegger
• Supervision Outgoing phase: Antonio Montalbán
• Supervision Return phase: Ekaterina Fokina

Talks

1. Recursive isomorphism and Turing equivalence through the effective descriptive set theory lens (Black board talk)
   Generalized Computability theory 2024, Castro Urdiales, Spain, 22.08.24
2. Algorithmic Aspects of Left-orderings of solvable Baumslag-Solitar groups via their dynamical realizations, [ Slides ]
   Computability in Europe, 11.07.2024
3. Learning equivalence relations on Polish spaces (Black board talk)
   Leeds Computability Days, University of Leeds, 02.07.2024
4. The Borel complexity of first-order theories [ Slides ]
   Logic Seminar, Ghent University, 06.03.2024
5. The Borel complexity of first-order theories [ Slides | Video ]
   Models of Peano Arithmetic seminar, City University of New York, 13.02.2024
6. The Borel complexity of first-order theories [ Slides | Video ]
   World Logic Day workshop, Nazarbayev University, 14.01.2024
7. Structural complexity notions for foundational theories [ Slides ]
   Logic Seminar, Kurt Gödel Research Center, 09.11.2023
8. Structural complexity notions for foundational theories [ Slides ]
   Pennstate Logic Seminar, 07.11.2023
9. Learning equivalence relations [ Slides ]
   Online Logic Seminar, 19.10.2023
10. The strong degrees of categoricity above 0" [ Slides ]
    Logic Seminar, University of Wisconsin at Madison, 18.04.2023
11. The strong degrees of categoricity above 0" [ Slides ]
    Logic Seminar, University of Michigan at Ann Arbor, 12.04.2023
12. Pairs of Structures: Variations and Application [ Slides ]
    Plenary Talk, ASL Annual Meeting 2023, UC Irvine, 28.03.2023
13. The strong degrees of categoricity above 0" [ Slides ]
    Logic Seminar, Iowa State University, 01.03.2023
14. The Structural Complexity of Models of Arithmetic [ Slides ]
    California State University, Northridge, 30.11.2022
15. Analytic complete equivalence relations and their degree spectra [ Slides ]
    Caltech Logic Seminar, 02.11.2022
16. The degrees of categoricity above 0 double jump [ Slides ]
    Logic Colloquium, University of California, Berkeley, 07.10.2022
17. The Structural Complexity of Models of Arithmetic [ Slides ]
    ASL Logic Colloquium 2022, Reykjavik, Iceland, 01.07.2022
18. The Structural Complexity of Models of Arithmetic [ Slides | Video ]
    Models of Peano Arithmetic seminar, City University of New York, 03.05.2022
19. The Structural Complexity of Models of Arithmetic [ Slides ]
    Computability Special Session, ASL Annual Meeting at Cornell University 2022, 09.04.2022
20. New Examples of Degrees of Categoricity [ Slides | Video ]
    Computability Theory and Applications, 02.11.2021

Publications

1. Hausdorff dimension and countable Borel equivalence relationsDOIarXiv
   Andrew Marks, Dino Rossegger, and Theodore Slaman
   Proceedings of the American Mathematical Society, vol. 154 (2), pp. 883-892 (2026)
2. Scott sentence complexities of linear orderingsDOIarXiv
   David Gonzalez and Dino Rossegger
   The Journal of Symbolic Logic, vol. 90 (4), pp. 1563-1592 (2025)
3. The Borel complexity of the class of models of first-order theoriesDOIarXiv
   Uri Andrews, David Gonzalez, Steffen Lempp, Dino Rossegger, and Hongyu Zhu
   Proceedings of the American Mathematical Society, vol. 153 (09), pp. 4013-4024 (2025)
4. Feferman's completeness theoremDOIarXiv
   Fedor Pakhomov, Michael Rathjen, and Dino Rossegger
   Bulletin of Symbolic Logic, vol. 31 (3), pp. 462-487 (2025)
5. Relations enumerable from positive informationDOIarXiv
   Barbara F Csima, Luke MacLean, and Dino Rossegger
   Journal of Logic and Computation, vol. 35 (5), pp. 1-15 (2025)
6. Learning Equivalence Relations on Polish SpacesDOIarXiv
   Dino Rossegger, Theodore Slaman, and Tomasz Steifer
   The Journal of Symbolic Logic, vol. first view, pp. 1-19 (2025)
7. A Lopez-Escobar Theorem for Continuous DomainsDOIarXiv
   Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger, Alexandra Soskova, and Stefan Vatev
   The Journal of Symbolic Logic, vol. 90 (2), pp. 854-871 (2025)
8. Degrees of categoricity and treeable degreesDOIarXiv
   Barbara F. Csima and Dino Rossegger
   Journal of Mathematical Logic, vol. 24 (03), pp. 2450002 (2024)
9. Learning Families of Algebraic Structures from TextDOIarXiv
   Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger, Alexandra Soskova, and Stefan Vatev
   Twenty Years of Theoretical and Practical Synergies, Computability in Europe, Lecture Notes in Computer Science, vol. 14773, pp. 166-178 (2024)
10. Algorithmic Aspects of Left-Orderings of Solvable Baumslag–Solitar Groups via its Dynamical RealizationDOIarXiv
    Meng-Che “Turbo” Ho, Khanh Le, and Dino Rossegger
    Twenty Years of Theoretical and Practical Synergies, Computability in Europe, Lecture Notes in Computer Science, vol. 14773, pp. 72-84 (2024)
11. The structural complexity of models of arithmeticDOIarXiv
    Antonio Montalbán and Dino Rossegger
    The Journal of Symbolic Logic, vol. 89 (4), pp. 1703-1719 (2024)
12. Degree spectra of analytic complete equivalence relationsDOIarXiv
    Dino Rossegger
    The Journal of Symbolic Logic, vol. 87 (4), pp. 1663-1676 (2022)