Constraint Satisfaction Problems for infinite homogeneous structures: towards algorithms
2020/37/B/ST6/01179
Keywords
Descriptors
- ST6_004: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna, algorytmy kwantowe
Panel
ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems
Host institution
Uniwersytet Jagielloński, Wydział Matematyki i Informatyki
Voivodeship: małopolskie
Principal investigator (from the host institution)
Number of co-investigators in the project: 3
Call
OPUS 19 – announced on 2020-03-16
- Amount awarded
- 331 932 PLN
- Project start date
- 2021-01-26
- Project end date
- 2026-01-25
- Project duration
- 60 months (the same as in the proposal)
- Project status
- Project completed
Project description
Download the project description in a pdf file
Note — project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.
Information in the final report
Publication in academic press/journals (1)
-
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough
- Authors:
- Antoine Mottet, Tomas Nagy, Michael Pinsker, Michal Wrona
- Academic press:
- SIAM J. Comput. (year: 2024, volume: 53(6), pages: 1709-1745), Publisher: Society for Industrial and Applied Mathematics
- Status:
- Published
- DOI:
- 10.1137/22m1538934 – link to the publication
Articles in post-conference publications (3)
-
Smooth Approximations and Relational Width Collapses
- Authors:
- Antoine Mottet, Tomás Nagy, Michael Pinsker, Michał Wrona
- Conference:
- 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) (year: 2021, volume: ICALP, pages: 138:1-138:20), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
- Date:
- conference 12.07-16.07.2021
- Status:
- Published
- DOI:
- 10.4230/LIPIcs.ICALP.2021.138 – link to the publication
-
The complete classification for quantified equality constraints
- Authors:
- Dmitriy Zhuk, Barnaby Martin, Michał Wrona
- Conference:
- Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 (year: 2023, volume: SODA, pages: 2746-2760), Publisher: SIAM
- Date:
- conference 22.01-25.01.2023
- Status:
- Published
- DOI:
- 10.1137/1.9781611977554.ch103 – link to the publication
-
Identifying Tractable Quantified Temporal Constraints Within Ord-Horn
- Authors:
- Jakub Rydval, Zaneta Semanisinova, Michał Wrona
- Conference:
- 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (year: 2024, volume: ICALP 2024, pages: 151:1--151:20), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
- Date:
- conference 08.07.24 - 12.07.24
- Status:
- Published
- DOI:
- 10.4230/LIPIcs.ICALP.2024.151 – link to the publication