11 Search Results for "Pinsker, Michael"

Document
DOI: 10.4230/LIPIcs.STACS.2026.15
The Complexity of Resilience for Digraph Queries

Authors: Manuel Bodirsky and Žaneta Semanišinová

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We prove a complexity dichotomy for the resilience problem for unions of conjunctive digraph queries (i.e., for existential positive sentences over the signature {R} of directed graphs). Specifically, for every union μ of conjunctive digraph queries, the following problem is in P or NP-complete: given a directed multigraph G and a natural number u, can we remove u edges from G so that G ⊧ ¬ μ? In fact, we verify a more general dichotomy conjecture from [Bodirsky et al., 2024] for all resilience problems in the special case of directed graphs, and show that for such unions of queries μ there exists a countably infinite (`dual') valued structure Δ_μ which either primitively positively constructs 1-in-3-3-SAT, and hence the resilience problem for μ is NP-complete by general principles, or has a pseudo cyclic canonical fractional polymorphism, and the resilience problem for μ is in P.
Cite as

Manuel Bodirsky and Žaneta Semanišinová. The Complexity of Resilience for Digraph Queries. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.STACS.2026.15,
  author =	{Bodirsky, Manuel and Semani\v{s}inov\'{a}, \v{Z}aneta},
  title =	{{The Complexity of Resilience for Digraph Queries}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.15},
  URN =		{urn:nbn:de:0030-drops-255045},
  doi =		{10.4230/LIPIcs.STACS.2026.15},
  annote =	{Keywords: valued constraints, unions of conjunctive queries, resilience, computational complexity, pp-constructions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.83
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Authors: Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. We provide answers to three fundamental questions on the scope of the Bodirsky-Pinsker conjecture. Our first two main results provide two simplifications of this scope, one of structural, and the other one of algebraic nature. The former simplification implies that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in the most powerful classification methods. The latter yields that the higher-arity invariants of any template within its scope can be assumed to be essentially injective, and any algebraic condition characterizing any complexity class within the conjecture closed under Datalog reductions must be satisfiable by injections, thus lifting the mystery of the better applicability of certain conditions over others. Our third main result uses the first one to show that any non-trivially tractable template within the scope serves, up to a Datalog-computable modification of it, as the witness of the tractability of a non-finitely tractable finite-domain Promise Constraint Satisfaction Problem (PCSP) by the so-called sandwich method. This generalizes a recent result of Mottet and provides a strong hitherto unknown connection between the Bodirsky-Pinsker conjecture and finite-domain PCSPs.
Cite as

Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess. Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pinsker_et_al:LIPIcs.MFCS.2025.83,
  author =	{Pinsker, Michael and Rydval, Jakub and Sch\"{o}bi, Moritz and Spiess, Christoph},
  title =	{{Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.83},
  URN =		{urn:nbn:de:0030-drops-241903},
  doi =		{10.4230/LIPIcs.MFCS.2025.83},
  annote =	{Keywords: (Promise) Constraint Satisfaction Problem, dichotomy conjecture, polymorphism, identity, algebraicity, homogeneity, \omega-categoricity, finite boundedness, Datalog}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.24
Temporal Valued Constraint Satisfaction Problems

Authors: Manuel Bodirsky, Édouard Bonnet, and Žaneta Semanišinová

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the computational complexity of the valued constraint satisfaction problem (VCSP) for every valued structure over ℚ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classical) constraint satisfaction problem: a relational structure is preserved by all order-preserving bijections if and only if all its relations have a first-order definition in (ℚ; <), and the CSPs for such structures are called temporal CSPs. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP. We prove that a temporal VCSP is in P, or NP-complete. Our analysis uses the concept of fractional polymorphisms. This is the first dichotomy result for VCSPs over infinite domains which is complete in the sense that it treats all valued structures that contain a given automorphism group.
Cite as

Manuel Bodirsky, Édouard Bonnet, and Žaneta Semanišinová. Temporal Valued Constraint Satisfaction Problems. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.MFCS.2025.24,
  author =	{Bodirsky, Manuel and Bonnet, \'{E}douard and Semani\v{s}inov\'{a}, \v{Z}aneta},
  title =	{{Temporal Valued Constraint Satisfaction Problems}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.24},
  URN =		{urn:nbn:de:0030-drops-241311},
  doi =		{10.4230/LIPIcs.MFCS.2025.24},
  annote =	{Keywords: Constraint Satisfaction Problems, valued CSPs, temporal CSPs, fractional polymorphisms, complexity dichotomy, min CSPs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.7
Sparser Abelian High Dimensional Expanders

Authors: Yotam Dikstein, Siqi Liu, and Avi Wigderson

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽₂ⁿ. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(n^ε) for every ε > 0, improving on a construction by Golowich [Golowich, 2023] which achieves ε = 1/2. [Golowich, 2023] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDX of any polynomial degree exp(ε n) for any constant ε > 0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [Liu et al., 2023]. Establishing coboundary expansion through Gromov’s "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.
Cite as

Yotam Dikstein, Siqi Liu, and Avi Wigderson. Sparser Abelian High Dimensional Expanders. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 7:1-7:98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.CCC.2025.7,
  author =	{Dikstein, Yotam and Liu, Siqi and Wigderson, Avi},
  title =	{{Sparser Abelian High Dimensional Expanders}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{7:1--7:98},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.7},
  URN =		{urn:nbn:de:0030-drops-237013},
  doi =		{10.4230/LIPIcs.CCC.2025.7},
  annote =	{Keywords: Local spectral expander, coboundary expander, Grassmannian expander}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.158
Restricted CSPs and F-Free Digraph Algorithmics

Authors: Santiago Guzmán-Pro and Barnaby Martin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to ℙ_k-free and ℙ_k-subgraph-free graphs. We consider the directed version of this research line, by addressing the question is it true that digraph homomorphism problems CSP(H) have a P versus NP-complete dichotomy when the input is restricted to ℙ→_k-free (resp. ℙ→_k-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(H) is NP-complete, then there is a positive integer N such that CSP(H) remains NP-hard even for ℙ→_N-subgraph-free digraphs. Moreover, CSP(H) becomes polynomial-time solvable for ℙ→_{N-1}-subgraph-free acyclic digraphs. We then verify the questions above for digraphs on three vertices and a family of smooth tournaments. We prove these results by establishing a connection between F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(H) restricted to yes-instances of CSP(H') - these were called restricted homomorphism problems by Hell and Nešetřil. Another main result of this paper presents a P versus NP-complete dichotomy for these problems. Moreover, this complexity dichotomy is accompanied by an algebraic dichotomy in the spirit of the finite domain CSP dichotomy.
Cite as

Santiago Guzmán-Pro and Barnaby Martin. Restricted CSPs and F-Free Digraph Algorithmics. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 158:1-158:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guzmanpro_et_al:LIPIcs.ICALP.2025.158,
  author =	{Guzm\'{a}n-Pro, Santiago and Martin, Barnaby},
  title =	{{Restricted CSPs and F-Free Digraph Algorithmics}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{158:1--158:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.158},
  URN =		{urn:nbn:de:0030-drops-235352},
  doi =		{10.4230/LIPIcs.ICALP.2025.158},
  annote =	{Keywords: Digraph homomorphisms, constraint satisfaction problems, subgraph-free algorithmics}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.140
Containment for Guarded Monotone Strict NP

Authors: Alexey Barsukov, Michael Pinsker, and Jakub Rydval

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment problem for GMSNP is decidable, thereby settling an open question of Bienvenu, ten Cate, Lutz, and Wolter, later restated by Bourhis and Lutz. Our proof also comes with a 2NEXPTIME upper bound on the complexity of the problem, which matches the lower bound for containment of MMSNP due to Bourhis and Lutz. In order to obtain these results, we significantly improve the state of knowledge of the model-theoretic properties of GMSNP. Bodirsky, Knäuer, and Starke previously showed that every GMSNP sentence defines a finite union of CSPs of ω-categorical structures. We show that these structures can be used to obtain a reduction from the containment problem for GMSNP to the much simpler problem of testing the existence of a certain map called recolouring, albeit in a more general setting than GMSNP; a careful analysis of this yields said upper bound. As a secondary contribution, we refine the construction of Bodirsky, Knäuer, and Starke by adding a restricted form of homogeneity to the properties of these structures, making the logic amenable to future complexity classifications for query evaluation using techniques developed for infinite-domain CSPs.
Cite as

Alexey Barsukov, Michael Pinsker, and Jakub Rydval. Containment for Guarded Monotone Strict NP. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 140:1-140:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barsukov_et_al:LIPIcs.ICALP.2025.140,
  author =	{Barsukov, Alexey and Pinsker, Michael and Rydval, Jakub},
  title =	{{Containment for Guarded Monotone Strict NP}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{140:1--140:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.140},
  URN =		{urn:nbn:de:0030-drops-235176},
  doi =		{10.4230/LIPIcs.ICALP.2025.140},
  annote =	{Keywords: guarded, monotone, SNP, forbidden patterns, query containment, recolouring, decidability, computational complexity, \omega-categoricity, constraint satisfaction, homogeneity, amalgamation property, Ramsey property, canonical function}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.13
Symmetric Linear Arc Monadic Datalog and Gadget Reductions

Authors: Manuel Bodirsky and Florian Starke

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three Datalog fragments that are particularly important for finite-domain constraint satisfaction: arc monadic Datalog, linear Datalog, and symmetric linear Datalog, each having good computational properties. We consider the fragment of Datalog where we impose all of these restrictions simultaneously, i.e., we study symmetric linear arc monadic (slam) Datalog. We characterise the CSPs that can be solved by a slam Datalog program as those that have a gadget reduction to a particular Boolean constraint satisfaction problem. We also present exact characterisations in terms of a homomorphism duality (which we call unfolded caterpillar duality), and in universal-algebraic terms (using known minor conditions, namely the existence of quasi Maltsev operations and k-absorptive operations of arity nk, for all n,k ≥ 1). Our characterisations also imply that the question whether a given finite-domain CSP can be expressed by a slam Datalog program is decidable.
Cite as

Manuel Bodirsky and Florian Starke. Symmetric Linear Arc Monadic Datalog and Gadget Reductions. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICDT.2025.13,
  author =	{Bodirsky, Manuel and Starke, Florian},
  title =	{{Symmetric Linear Arc Monadic Datalog and Gadget Reductions}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.13},
  URN =		{urn:nbn:de:0030-drops-229548},
  doi =		{10.4230/LIPIcs.ICDT.2025.13},
  annote =	{Keywords: Datalog, Gadget Reductions, Homomorphism Dualities, Minor Conditions}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.148
An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs

Authors: Antoine Mottet, Tomáš Nagy, and Michael Pinsker

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC'11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP'16) on graph satisfiability.
Cite as

Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148,
  author =	{Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael},
  title =	{{An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{148:1--148:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.148},
  URN =		{urn:nbn:de:0030-drops-202912},
  doi =		{10.4230/LIPIcs.ICALP.2024.148},
  annote =	{Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.138
Smooth Approximations and Relational Width Collapses

Authors: Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n ≥ 3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al.. In particular, the bounded width hierarchy collapses in those cases as well.
Cite as

Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona. Smooth Approximations and Relational Width Collapses. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.ICALP.2021.138,
  author =	{Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael and Wrona, Micha{\l}},
  title =	{{Smooth Approximations and Relational Width Collapses}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{138:1--138:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.138},
  URN =		{urn:nbn:de:0030-drops-142075},
  doi =		{10.4230/LIPIcs.ICALP.2021.138},
  annote =	{Keywords: local consistency, bounded width, constraint satisfaction problems, polymorphisms, smooth approximations}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.131
Hrushovski’s Encoding and ω-Categorical CSP Monsters

Authors: Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction - a refinement of an encoding due to Hrushosvki - to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and ω-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.
Cite as

Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. Hrushovski’s Encoding and ω-Categorical CSP Monsters. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 131:1-131:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gillibert_et_al:LIPIcs.ICALP.2020.131,
  author =	{Gillibert, Pierre and Jonu\v{s}as, Julius and Kompatscher, Michael and Mottet, Antoine and Pinsker, Michael},
  title =	{{Hrushovski’s Encoding and \omega-Categorical CSP Monsters}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{131:1--131:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.131},
  URN =		{urn:nbn:de:0030-drops-125387},
  doi =		{10.4230/LIPIcs.ICALP.2020.131},
  annote =	{Keywords: Constraint satisfaction problem, complexity, polymorphism, pointwise convergence topology, height 1 identity, \omega-categoricity, orbit growth}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.119
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Authors: Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with domain Hn whose relations are first-order definable in (Hn, E) the constraint satisfaction problem for Gamma is either in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.
Cite as

Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 119:1-119:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2016.119,
  author =	{Bodirsky, Manuel and Martin, Barnaby and Pinsker, Michael and Pongr\'{a}cz, Andr\'{a}s},
  title =	{{Constraint Satisfaction Problems for Reducts of Homogeneous Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{119:1--119:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.119},
  URN =		{urn:nbn:de:0030-drops-62543},
  doi =		{10.4230/LIPIcs.ICALP.2016.119},
  annote =	{Keywords: Constraint Satisfaction, Homogeneous Graphs, Computational Complexity, Universal Algebra, Ramsey Theory}
}
  • Refine by Type
  • 11 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 6 2025
  • 1 2024
  • 1 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 6 Pinsker, Michael
  • 4 Bodirsky, Manuel
  • 3 Mottet, Antoine
  • 2 Martin, Barnaby
  • 2 Nagy, Tomáš
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Logic
  • 2 Theory of computation → Complexity theory and logic
  • 2 Theory of computation → Computational complexity and cryptography
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 3 ω-categoricity
  • 2 Constraint Satisfaction Problems
  • 2 Datalog
  • 2 computational complexity
  • 2 constraint satisfaction problems
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact