Towards infinite PCSP : a dichotomy for monochromatic cliques

2026
book section
conference proceedings
dc.abstract.enThe 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).
dc.affiliationSzkoła Doktorska Nauk Ścisłych i Przyrodniczych
dc.conference41st Annual Symposium on Logic in Computer Science (LICS 2026)
dc.conference.cityLizbona
dc.conference.countryPortugalia
dc.conference.datefinish2026-07-23
dc.conference.datestart2026-07-20
dc.conference.seriesIEEE Symposium on Logic in Computer Science
dc.conference.seriesshortcutLICS
dc.conference.shortcutLICS 2026
dc.conference.weblinkhttps://drops.dagstuhl.de/entities/volume/LIPIcs-volume
dc.contributor.authorBanakh, Demian - 406982
dc.contributor.authorBarsukov, Alexey
dc.contributor.authorNakajima, Tamio-Vesa
dc.date.accession2026-07-16
dc.date.accessioned2026-07-16T07:35:07Z
dc.date.available2026-07-16T07:35:07Z
dc.date.createdat2026-07-10T08:47:33Zen
dc.date.issued2026
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternational
dc.description.physical13:1-13:28
dc.description.seriesLeibniz International Proceedings in Informatics (LIPIcs)
dc.description.versionostateczna wersja wydawcy
dc.identifier.bookweblinkhttps://ruj.uj.edu.pl/handle/item/579518
dc.identifier.doi10.4230/LIPIcs.LICS.2026.13
dc.identifier.projectDRC AI
dc.identifier.urihttps://ruj.uj.edu.pl/handle/item/579518
dc.identifier.weblinkhttps://doi.org/10.4230/LIPIcs.LICS.2026.13
dc.languageeng
dc.language.containereng
dc.placeSchloss Dagstuhl
dc.publisherLeibniz-Zentrum für Informatik
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.typeinne
dc.source.integratorfalse
dc.subject.enpromise constraint satisfaction problem
dc.subject.enmmsnp
dc.subject.enapproximation algorithms
dc.subject.enrainbow colouring
dc.subtypeConferenceProceedings
dc.titleTowards infinite PCSP : a dichotomy for monochromatic cliques
dc.title.container41st Annual Symposium on Logic in Computer Science (LICS 2026)
dc.typeBookSection
dspace.entity.typePublicationen
dc.abstract.en
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).
dc.affiliation
Szkoła Doktorska Nauk Ścisłych i Przyrodniczych
dc.conference
41st Annual Symposium on Logic in Computer Science (LICS 2026)
dc.conference.city
Lizbona
dc.conference.country
Portugalia
dc.conference.datefinish
2026-07-23
dc.conference.datestart
2026-07-20
dc.conference.series
IEEE Symposium on Logic in Computer Science
dc.conference.seriesshortcut
LICS
dc.conference.shortcut
LICS 2026
dc.conference.weblink
https://drops.dagstuhl.de/entities/volume/LIPIcs-volume
dc.contributor.author
Banakh, Demian - 406982
dc.contributor.author
Barsukov, Alexey
dc.contributor.author
Nakajima, Tamio-Vesa
dc.date.accession
2026-07-16
dc.date.accessioned
2026-07-16T07:35:07Z
dc.date.available
2026-07-16T07:35:07Z
dc.date.createdaten
2026-07-10T08:47:33Z
dc.date.issued
2026
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.conftype
international
dc.description.physical
13:1-13:28
dc.description.series
Leibniz International Proceedings in Informatics (LIPIcs)
dc.description.version
ostateczna wersja wydawcy
dc.identifier.bookweblink
https://ruj.uj.edu.pl/handle/item/579518
dc.identifier.doi
10.4230/LIPIcs.LICS.2026.13
dc.identifier.project
DRC AI
dc.identifier.uri
https://ruj.uj.edu.pl/handle/item/579518
dc.identifier.weblink
https://doi.org/10.4230/LIPIcs.LICS.2026.13
dc.language
eng
dc.language.container
eng
dc.place
Schloss Dagstuhl
dc.publisher
Leibniz-Zentrum für Informatik
dc.rights
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licence
CC-BY
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.type
inne
dc.source.integrator
false
dc.subject.en
promise constraint satisfaction problem
dc.subject.en
mmsnp
dc.subject.en
approximation algorithms
dc.subject.en
rainbow colouring
dc.subtype
ConferenceProceedings
dc.title
Towards infinite PCSP : a dichotomy for monochromatic cliques
dc.title.container
41st Annual Symposium on Logic in Computer Science (LICS 2026)
dc.type
BookSection
dspace.entity.typeen
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
7
Views per month
Views per city
Krakow
6