44 Search Results for "Krokhin, Andrei"

Volume

Dagstuhl Follow-Ups, Volume 7

The Constraint Satisfaction Problem: Complexity and Approximability

Editors: Andrei Krokhin and Stanislav Zivny

Document
DOI: 10.4230/LIPIcs.STACS.2026.22
Modular Counting over 3-Element and Conservative Domains

Authors: Andrei A. Bulatov and Amirhossein Kazeminia

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

Abstract
In the Constraint Satisfaction Problem (CSP for short) the goal is to decide the existence of a homomorphism from a given relational structure {G} to a given relational structure {H}. If the structure {H} is fixed and {G} is the only input, the problem is denoted CSP({H}). In its counting version, #CSP({H}), the task is to find the number of such homomorphisms. The CSP and #CSP have been used to model a wide variety of combinatorial problems and have received a tremendous amount of attention from researchers from multiple disciplines. In this paper we consider the modular version of the counting CSPs, that is, problems of the form #_pCSP({H}) of counting the number of homomorphisms to {H} modulo a fixed prime number p. Modular counting has been intensively studied during the last decade, although mainly in the case of graph homomorphisms. Here we continue the program of systematic research of modular counting of homomorphisms to general relational structures. The main results of the paper include a new way of reducing modular counting problems to smaller domains and a study of the complexity of such problems over 3-element domains and over conservative domains, that is, relational structures that allow to express (in a certain exact way) every possible unary predicate.
Cite as

Andrei A. Bulatov and Amirhossein Kazeminia. Modular Counting over 3-Element and Conservative Domains. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2026.22,
  author =	{Bulatov, Andrei A. and Kazeminia, Amirhossein},
  title =	{{Modular Counting over 3-Element and Conservative Domains}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-255114},
  doi =		{10.4230/LIPIcs.STACS.2026.22},
  annote =	{Keywords: Constraint Satisfaction Problem, Modular Counting}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.9
Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms

Authors: Anuj Dawar, Lauri Hella, and Benedikt Pago

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
We investigate the expressive power of generalized quantifiers closed under partial polymorphism conditions motivated by the study of constraint satisfaction problems. We answer a number of questions arising from the work of Dawar and Hella (CSL 2024) where such quantifiers were introduced. For quantifiers closed under partial near-unanimity polymorphisms, we establish hierarchy results clarifying the interplay between the arity of the polymorphisms and of the quantifiers: The expressive power of (𝓁+1)-ary quantifiers closed under 𝓁-ary partial near-unanimity polymorphisms is strictly between the class of all quantifiers of arity 𝓁-1 and 𝓁. We also establish an infinite hierarchy based on the arity of quantifiers with a fixed arity of partial near-unanimity polymorphisms. Finally, we prove inexpressiveness results for quantifiers with a partial Maltsev polymorphism. The separation results are proved using novel algebraic constructions in the style of Cai-Fürer-Immerman and the quantifier pebble games of Dawar and Hella (2024).
Cite as

Anuj Dawar, Lauri Hella, and Benedikt Pago. Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2026.9,
  author =	{Dawar, Anuj and Hella, Lauri and Pago, Benedikt},
  title =	{{Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.9},
  URN =		{urn:nbn:de:0030-drops-254330},
  doi =		{10.4230/LIPIcs.CSL.2026.9},
  annote =	{Keywords: finite model theory, constraint satisfaction problems, generalized quantifiers}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.66
A Parameterized-Complexity Framework for Finding Local Optima

Authors: Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood. The traditional frameworks, PLS and the standard algorithm problem, introduced by Johnson, Papadimitriou, and Yannakakis (1988) fail to capture the methodology of local search algorithms: PLS is concerned with finding a local optimum and not with using local search, while the standard algorithm problem restricts each improvement step to follow a fixed pivoting rule. In this work, we introduce a novel formulation of local search which provides a middle ground between these models. In particular, the task is to output not only a local optimum but also a chain of local improvements leading to it. With this framework, we aim to capture the challenge in designing a good pivoting rule. Especially, when combined with the parameterized complexity paradigm, it enables both strong lower bounds and meaningful tractability results. Unlike previous works that combined parameterized complexity with local search, our framework targets the whole task of finding a local optimum and not only a single improvement step. Focusing on two representative meta-problems - Subset Weight Optimization Problem with the c-swap neighborhood and Weighted Circuit with the flip neighborhood - we establish fixed-parameter tractability results related to the number of distinct weights, while ruling out an analogous result when parameterizing by the distance to the nearest optimum via a new type of reduction.
Cite as

Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz. A Parameterized-Complexity Framework for Finding Local Optima. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ITCS.2026.66,
  author =	{Ganian, Robert and Hoang, Hung P. and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{A Parameterized-Complexity Framework for Finding Local Optima}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{66:1--66:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.66},
  URN =		{urn:nbn:de:0030-drops-253532},
  doi =		{10.4230/LIPIcs.ITCS.2026.66},
  annote =	{Keywords: Local Search, Parameterized Complexity, PLS}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.26
Complexity of Local Search for CSPs Parameterized by Constraint Difference

Authors: Aditya Anand, Vincent Cohen-Addad, Tommaso D'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset S of a universe U, the new input consists of a current solution P (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution S^*, the goal is to find a feasible solution as good as S^* in parameterized time f(k)⋅n^O(1), where k denotes the distance |PΔ S^*|. This model generalizes numerous classical parameterized optimization problems whose parameter k is the minimum number of elements removed from U to make it feasible, which corresponds to the case P = U. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where U is the set of constraints, and a subset U' of constraints is feasible if there is an assignment to the variables satisfying all constraints in U'. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate’s acceptance depends on the number of true literals.
Cite as

Aditya Anand, Vincent Cohen-Addad, Tommaso D'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng. Complexity of Local Search for CSPs Parameterized by Constraint Difference. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.IPEC.2025.26,
  author =	{Anand, Aditya and Cohen-Addad, Vincent and D'Orsi, Tommaso and Gupta, Anupam and Lee, Euiwoong and Panigrahi, Debmalya and Peng, Sijin},
  title =	{{Complexity of Local Search for CSPs Parameterized by Constraint Difference}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.26},
  URN =		{urn:nbn:de:0030-drops-251586},
  doi =		{10.4230/LIPIcs.IPEC.2025.26},
  annote =	{Keywords: Constraint Satisfaction Problems, Parameterized Local Search, Optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.88
Parameterized Approximability for Modular Linear Equations

Authors: Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the Min-r-Lin(ℤ_m) problem: given a system S of length-r linear equations modulo m, find Z ⊆ S of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate in polynomial time within any constant factor even when r = m = 2. We focus on parameterized approximation with solution size as the parameter. Dabrowski, Jonsson, Ordyniak, Osipov and Wahlström [SODA-2023] showed that Min-r-Lin(ℤ_m) is in FPT if m is prime (i.e. ℤ_m is a field), and it is W[1]-hard if m is not a prime power. We show that Min-r-Lin(ℤ_{pⁿ}) is FPT-approximable within a factor of 2 for every prime p and integer n ≥ 2. This implies that Min-2-Lin(ℤ_m), m ∈ ℤ^+, is FPT-approximable within a factor of 2ω(m) where ω(m) counts the number of distinct prime divisors of m. The high-level idea behind the algorithm is to solve tighter and tighter relaxations of the problem, decreasing the set of possible values for the variables at each step. When working over ℤ_{pⁿ} and viewing the values in base-p, one can roughly think of a relaxation as fixing the number of trailing zeros and the least significant nonzero digits of the values assigned to the variables. To solve the relaxed problem, we construct a certain graph where solutions can be identified with a particular collection of cuts. The relaxation may hide obstructions that will only become visible in the next iteration of the algorithm, which makes it difficult to find optimal solutions. To deal with this, we use a strategy based on shadow removal [Marx & Razgon, STOC-2011] to compute solutions that (1) cost at most twice as much as the optimum and (2) allow us to reduce the set of values for all variables simultaneously. We complement the algorithmic result with two lower bounds, ruling out constant-factor FPT-approximation for Min-3-Lin(R) over any nontrivial ring R and for Min-2-Lin(R) over some finite commutative rings R.
Cite as

Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Parameterized Approximability for Modular Linear Equations. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 88:1-88:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dabrowski_et_al:LIPIcs.ESA.2025.88,
  author =	{Dabrowski, Konrad K. and Jonsson, Peter and Ordyniak, Sebastian and Osipov, George and Wahlstr\"{o}m, Magnus},
  title =	{{Parameterized Approximability for Modular Linear Equations}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{88:1--88:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.88},
  URN =		{urn:nbn:de:0030-drops-245562},
  doi =		{10.4230/LIPIcs.ESA.2025.88},
  annote =	{Keywords: parameterized complexity, approximation algorithms, linear equations}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.3
Maximum And- vs. Even-SAT

Authors: Tamio-Vesa Nakajima and Stanislav Živný

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
A multiset of literals, called a clause, is strongly satisfied by an assignment if no literal evaluates to false. Finding an assignment that maximises the number of strongly satisfied clauses is NP-hard. We present a simple algorithm that finds, given a multiset of clauses that admits an assignment that strongly satisfies ρ of the clauses, an assignment in which at least ρ of the clauses are weakly satisfied, in the sense that an even number of literals evaluate to false. In particular, this implies an efficient algorithm for finding an undirected cut of value ρ in a graph G given that a directed cut of value ρ in G is promised to exist. A similar argument also gives an efficient algorithm for finding an acyclic subgraph of G with ρ edges under the same promise.
Cite as

Tamio-Vesa Nakajima and Stanislav Živný. Maximum And- vs. Even-SAT. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 3:1-3:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.APPROX/RANDOM.2025.3,
  author =	{Nakajima, Tamio-Vesa and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Maximum And- vs. Even-SAT}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{3:1--3:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.3},
  URN =		{urn:nbn:de:0030-drops-243696},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.3},
  annote =	{Keywords: approximation, promise constraint satisfaction, max and, max even, max cut, max dicut, max acyclic}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.19
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

Authors: Ian DeHaan, Neng Huang, and Euiwoong Lee

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language Γ which has the dual discriminator operation as a polymorphism, there exists a |D|-approximation algorithm for MinCostCSP(Γ) where D is the domain. Complementing our algorithmic result, we show that any constraint language Γ where MinCostCSP(Γ) admits a constant-factor approximation must have a near-unanimity (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP(Γ) has an NU polymorphism and is |D|-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.
Cite as

Ian DeHaan, Neng Huang, and Euiwoong Lee. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dehaan_et_al:LIPIcs.APPROX/RANDOM.2025.19,
  author =	{DeHaan, Ian and Huang, Neng and Lee, Euiwoong},
  title =	{{On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  URN =		{urn:nbn:de:0030-drops-243851},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  annote =	{Keywords: Constraint satisfaction problems, approximation algorithms, polymorphisms}
}
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.37
New Hardness Results for Low-Rank Matrix Completion

Authors: Dror Chawin and Ishay Haviv

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

Abstract
The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new NP-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number ε ∈ [2^{-O(d)},1/7], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is NP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most ε, even when the rank is allowed to exceed d by a multiplicative factor of O (1/(ε²⋅log(1/ε))). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to ε that decays polynomially in d. We establish similar NP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.
Cite as

Dror Chawin and Ishay Haviv. New Hardness Results for Low-Rank Matrix Completion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.MFCS.2025.37,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{New Hardness Results for Low-Rank Matrix Completion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{37:1--37:18},
  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.37},
  URN =		{urn:nbn:de:0030-drops-241448},
  doi =		{10.4230/LIPIcs.MFCS.2025.37},
  annote =	{Keywords: hardness of approximation, low-rank matrix completion, graph coloring}
}
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
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.166
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems

Authors: Moritz Lichter and Benedikt Pago

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

Abstract
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tractable and not even all Maltsev CSPs. This rules them out as candidates for a universal polynomial-time CSP algorithm. The algorithms are ℤ-affine k-consistency, BLP+AIP, BA^{k}, and CLAP. We thereby answer a question by Brakensiek, Guruswami, Wrochna, and Živný [Joshua Brakensiek et al., 2020] whether a constant level of BA^{k}solves all tractable CSPs in the negative: Indeed, not even a sublinear level k suffices. We also refute a conjecture by Dalmau and Opršal [Víctor Dalmau and Jakub Opršal, 2024] (LICS 2024) that every CSP is either solved by ℤ-affine k-consistency or admits a Datalog reduction from 3-colorability. For the cohomological k-consistency algorithm, that is also based on affine relaxations, we show that it correctly solves our counterexample but fails on an NP-complete template.
Cite as

Moritz Lichter and Benedikt Pago. Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 166:1-166:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lichter_et_al:LIPIcs.ICALP.2025.166,
  author =	{Lichter, Moritz and Pago, Benedikt},
  title =	{{Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{166:1--166:17},
  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.166},
  URN =		{urn:nbn:de:0030-drops-235431},
  doi =		{10.4230/LIPIcs.ICALP.2025.166},
  annote =	{Keywords: constraint satisfaction, affine relaxation, promise CSPs, \mathbb{Z}-affine k-consistency, cohomological k-consistency algorithm, Tseitin, graph isomorphism}
}
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 A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.34
On the Degree Automatability of Sum-Of-Squares Proofs

Authors: Alex Bortolotti, Monaldo Mastrolilli, and Luis Felipe Vargas

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

Abstract
The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has emerged as a promising tool in optimization. However, it remains unclear whether fixed-degree SoS proofs can be automated [O'Donnell (2017)]. Indeed, there are examples of polynomial systems with bounded coefficients that admit low-degree SoS proofs, but these proofs necessarily involve numbers with an exponential number of bits, implying that low-degree SoS proofs cannot always be found efficiently. A sufficient condition derived from the Nullstellensatz proof system [Raghavendra and Weitz (2017)] identifies cases where bit complexity issues can be circumvented. One of the main problems left open by Raghavendra and Weitz is proving any result for refutations, as their condition applies only to polynomial systems with a large set of solutions. In this work, we broaden the class of polynomial systems for which degree-d SoS proofs can be automated. To achieve this, we develop a new criterion and we demonstrate how our criterion applies to polynomial systems beyond the scope of Raghavendra and Weitz’s result. In particular, we establish a separation for instances arising from Constraint Satisfaction Problems (CSPs). Moreover, our result extends to refutations, establishing that polynomial-time refutation is possible for broad classes of polynomial time solvable constraint problems, highlighting a first advancement in this area.
Cite as

Alex Bortolotti, Monaldo Mastrolilli, and Luis Felipe Vargas. On the Degree Automatability of Sum-Of-Squares Proofs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bortolotti_et_al:LIPIcs.ICALP.2025.34,
  author =	{Bortolotti, Alex and Mastrolilli, Monaldo and Vargas, Luis Felipe},
  title =	{{On the Degree Automatability of Sum-Of-Squares Proofs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{34:1--34:19},
  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.34},
  URN =		{urn:nbn:de:0030-drops-234110},
  doi =		{10.4230/LIPIcs.ICALP.2025.34},
  annote =	{Keywords: Sum of squares, Polynomial calculus, Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems, Proof complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.37
Satisfiability of Commutative vs. Non-Commutative CSPs

Authors: Andrei A. Bulatov and Stanislav Živný

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

Abstract
The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hilbert space of dimension four. A natural question is then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis, and Severini answered this question for all Boolean Constraint Satisfaction Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual Horn-SAT, classical satisfiability and operator satisfiability is the same and thus there is no gap; for all other Boolean CSPs, these notions differ as there are gaps, i.e., there are unsatisfiable instances that are satisfiable via operators on Hilbert spaces. We generalize their result to CSPs on arbitrary finite domains and give an almost complete classification: First, we show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show that tractable CSPs of unbounded width can simulate, in a satisfiability-gap-preserving fashion, linear equations over an Abelian group of prime order p; for such CSPs, we obtain a separation of classical satisfiability and satisfiability via operators on infinite-dimensional Hilbert spaces. Furthermore, if p = 2, such CSPs also have gaps separating classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces.
Cite as

Andrei A. Bulatov and Stanislav Živný. Satisfiability of Commutative vs. Non-Commutative CSPs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.ICALP.2025.37,
  author =	{Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Satisfiability of Commutative vs. Non-Commutative CSPs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{37:1--37:18},
  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.37},
  URN =		{urn:nbn:de:0030-drops-234149},
  doi =		{10.4230/LIPIcs.ICALP.2025.37},
  annote =	{Keywords: constraint satisfaction, quantum CSP, operator CSP}
}
  • Refine by Type
  • 43 Document/PDF
  • 20 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 3 2026
  • 17 2025
  • 1 2021
  • 15 2017
  • 1 2016
  • Show More...

  • Refine by Author
  • 9 Krokhin, Andrei
  • 6 Bulatov, Andrei A.
  • 4 Zivny, Stanislav
  • 4 Živný, Stanislav
  • 3 Bodirsky, Manuel
  • Show More...

  • Refine by Series/Journal
  • 22 LIPIcs
  • 2 DagRep
  • 14 DFU
  • 5 DagSemProc

  • Refine by Classification
  • 9 Theory of computation → Problems, reductions and completeness
  • 4 Theory of computation → Constraint and logic programming
  • 4 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Finite Model Theory
  • 3 Theory of computation → Complexity theory and logic
  • Show More...

  • Refine by Keyword
  • 11 Constraint satisfaction problems
  • 4 Computational complexity
  • 3 CSP dichotomy conjecture
  • 3 Constraint satisfaction problem (CSP)
  • 3 Datalog
  • 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