Library

Algebraic and model theoretic methods in constraint satisfaction

This text is related to the tutorials I gave at the Banff International Research Station and within a "Doc-course" at Charles University Prague in the fall of 2014. It describes my current research and some of the most important open questions related to it.

MathematicsComputer Science
Source

Paper

References (45)

01Model TheoryDavid Marker, Alessandro Berarducci, Emmanuel Breuillard et al.2018 · The Incompleteness Phenomenon · 3.1k citations
02Reconstructing the topology of clonesM. Bodirsky, M. Pinsker, András Pongrácz2013 · arXiv.org · 42 citations
03Ramsey Precompact Expansions of Homogeneous Directed GraphsJ. Jasinski, C. Laflamme, Lionel Nguyen Van Thé et al.2013 · Electronic Journal of Combinatorics · 29 citations
04The 42 reducts of the random ordered graphM. Bodirsky, M. Pinsker, Andr'as Pongr'acz2013 · 38 citations
05On vertex sparsifiers with Steiner nodesJulia Chuzhoy2012 · Symposium on the Theory of Computing · 150 citations
06Complexity Classification in Infinite-Domain Constraint SatisfactionM. Bodirsky2012 · arXiv.org · 100 citations In Library
07Reducts of the random partial orderP'eter P'al Pach, M. Pinsker, Gabriella Pluhár et al.2011 · 40 citations
08Reducts of Ramsey structuresM. Bodirsky, M. Pinsker2011 · AMS-ASL Joint Special Session · 76 citations
09Tractable Set ConstraintsM. Bodirsky, Martin Hils, Alex Krimkevitch2011 · International Joint Conference on Artificial Intelligence · 12 citations In Library
10Decidability of DefinabilityM. Bodirsky, M. Pinsker, T. Tsankov2010 · 2011 IEEE 26th Annual Symposium on Logic in Computer Science · 114 citations
11Schaefer's theorem for graphsM. Bodirsky, M. Pinsker2010 · Symposium on the Theory of Computing · 101 citations
12Minimal functions on the random graphM. Bodirsky, M. Pinsker2010 · Israel Journal of Mathematics · 42 citations

Scroll for more · 33 remaining

Similar papers

Conversational Modeling for Constraint SatisfactionEugene C. Freuder2024 · Proceedings of the AAAI Conference on Artificial Intelligence · 4 citations In Library
Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction ProblemsBiman Roy2020 · Linköping studies in science and technology, Dissertations · 1 citation In Library
Complexity of Infinite-Domain Constraint SatisfactionM. Bodirsky2021 · 101 citations In Library
Constraint Satisfaction Techniques for Combinatorial ProblemsD. E. Narváez2018 · AAAI Conference on Artificial Intelligence · 3 citations In Library
Algebraic Properties of Valued Constraint Satisfaction ProblemM. Kozik, Joanna Ochremiak2014 · International Colloquium on Automata, Languages and Programming · 44 citations In Library
A categorical perspective on constraint satisfaction: The wonderland of adjunctionsMaximilian Hadek, Tomás Jakl, Jakub Opršal2025 · arXiv.org · 3 citations In Library
Automated Modelling and Solving in Constraint ProgrammingB. O’Sullivan2010 · AAAI Conference on Artificial Intelligence · 47 citations In Library
Democratizing Constraint Satisfaction Problems through Machine LearningMohit Kumar, Samuel Kolb, Clément Gautrais et al.2021 · AAAI Conference on Artificial Intelligence · 2 citations In Library
A Meta-Heuristic Approach for The Constraint Satisfaction ProblemTianci Chen, Xinyun Wu2020 · IEEE International Conference on Electronics Information and Emergency Communication · 0 citations In Library
Chapter 33. Satisfiability Modulo TheoriesClark Barrett, Roberto Sebastiani, Sanjit A. Seshia et al.2021 · Frontiers in artificial intelligence and applications In Library
© 2026 NYSGPT2525 LLC