Metraipolis › archive › dc_5edaae07480c
A Fast Algorithm for Maltsev Constraints — arXiv:2610.08207
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.08207
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:40:39.386Z
- SHA-256 of the archived text
2133a2763186107d2b5e8516fae3feb8b88f63ae3f6eea66637d0f40e39c9d1d- Stable URL of this page
https://metraipolis.com/documento/dc_5edaae07480c
How to cite
A Fast Algorithm for Maltsev Constraints — arXiv:2610.08207 — arXiv (en), https://arxiv.org/abs/2610.08207 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5edaae07480c (Metraipolis archive dc_5edaae07480c, sha256 2133a2763186107d2b5e8516fae3feb8b88f63ae3f6eea66637d0f40e39c9d1d)
BibTeX
@misc{dc5edaae07480c,
title = {A Fast Algorithm for Maltsev Constraints — arXiv:2610.08207},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.08207},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5edaae07480c; sha256 2133a2763186107d2b5e8516fae3feb8b88f63ae3f6eea66637d0f40e39c9d1d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08207. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The constraint satisfaction problem over a set of relations $\Gamma$ (CSP($\Gamma$)) is the computational problem of deciding if a set of constraints admits at least one solution. The classical complexity for finite-domain CSP($\Gamma$) is settled by the CSP dichotomy theorem: it is tractable if $\Gamma$ satisfies a non-trivial algebraic invariant and is NP-complete otherwise. However, not all these algebraic invariants result in efficient algorithms despite being theoretically tractable. A notable case that generalizes linear equations is that of Maltsev CSPs: an $n$-variable instance with $m$ constraints is solvable in roughly $O(n^8 \cdot m)$ time by Bulatov and Dalmau (SIAM J. Comput. 2006) or $O(n^4 \cdot m)$ time by Dyer and Richerby (SIAM J. Comput. 2013). At the same time, arguably, most "natural" and efficiently usable polynomial-time algorithms rarely exceed a quadratic or cubic time bound. In this paper we revisit Maltsev constraints with this question in mind and find a $O(n^2 \cdot m)$ algorithm (for finite languages, for infinite languages we in addition need to take the total size of the instance into account). The main novel idea is to not attempt to improve the bottleneck in Bulatov and Dalmau (the Fix-Values procedure) but to avoid it altogether with a slightly more refined approach that allows us to search through a smaller space. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2610.08207 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T13:13:03.937Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).