Search Results

Documents authored by Barsukov, Alexey

Document
DOI: 10.4230/LIPIcs.LICS.2026.13
Towards Infinite PCSP: A Dichotomy for Monochromatic Cliques

Authors: Demian Banakh, Alexey Barsukov, and Tamio-Vesa Nakajima

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs) modulo polynomial-time reductions. At the same time, MMSNP contains many problems that are expressible as ω-categorical CSPs but not as finite-domain ones. We initiate the study of Promise MMSNP (PMMSNP), a promise analogue of MMSNP. We show that every PMMSNP problem is poly-time equivalent to a (finite-domain) Promise CSP (PCSP), thereby extending the classical MMSNP-CSP correspondence to the promise setting. We then investigate the complexity of PMMSNPs arising from forbidding monochromatic cliques, a class encompassing promise graph colouring problems. For this class, we obtain a full complexity classification conditional on the Rich 2-to-1 Conjecture, a recently proposed perfect-completeness surrogate of the Unique Games Conjecture. As a key intermediate step which may be of independent interest, we prove that it is NP-hard, under the Rich 2-to-1 Conjecture, to properly colour a uniform hypergraph even if it is promised to admit a colouring satisfying a certain technical condition called reconfigurability. This proof is an extension of the recent work of Braverman, Khot, Lifshitz and Minzer (Adv. Math. 2025). To illustrate the broad applicability of this theorem, we show that it implies most of the linearly-ordered colouring conjecture of Barto, Battistelli, and Berg (STACS 2021).
Cite as

Demian Banakh, Alexey Barsukov, and Tamio-Vesa Nakajima. Towards Infinite PCSP: A Dichotomy for Monochromatic Cliques. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 13:1-13:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{banakh_et_al:LIPIcs.LICS.2026.13,
  author =	{Banakh, Demian and Barsukov, Alexey and Nakajima, Tamio-Vesa},
  title =	{{Towards Infinite PCSP: A Dichotomy for Monochromatic Cliques}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{13:1--13:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.13},
  URN =		{urn:nbn:de:0030-drops-268000},
  doi =		{10.4230/LIPIcs.LICS.2026.13},
  annote =	{Keywords: Promise Constraint Satisfaction Problem, MMSNP, Approximation Algorithms, Rainbow Colouring}
}
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}
}
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