Search Results

Documents authored by Barto, Libor

Document
DOI: 10.4230/LIPIcs.CP.2022.2
Fixed-Template Promise Model Checking Problems

Authors: Kristina Asimi, Libor Barto, and Silvia Butti

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure (also called model). We study a class of problems that generalizes the CSP simultaneously in two directions: we fix a set ℒ of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak. Given a sentence which only uses symbols from ℒ, the task is to distinguish whether the sentence is true in the strong sense, or it is false even in the weak sense. We classify the computational complexity of these problems for the existential positive equality-free fragment of first-order logic, i.e., ℒ = {∃,∧,∨}, and we prove some upper and lower bounds for the positive equality-free fragment, ℒ = {∃,∀,∧,∨}. The partial results are sufficient, e.g., for all extensions of the latter fragment.
Cite as

Kristina Asimi, Libor Barto, and Silvia Butti. Fixed-Template Promise Model Checking Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{asimi_et_al:LIPIcs.CP.2022.2,
  author =	{Asimi, Kristina and Barto, Libor and Butti, Silvia},
  title =	{{Fixed-Template Promise Model Checking Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.2},
  URN =		{urn:nbn:de:0030-drops-166310},
  doi =		{10.4230/LIPIcs.CP.2022.2},
  annote =	{Keywords: Model Checking Problem, First-Order Logic, Promise Constraint Satisfaction Problem, Multi-Homomorphism}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.4
Weisfeiler-Leman Invariant Promise Valued CSPs

Authors: Libor Barto and Silvia Butti

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivalent to the basic linear programming relaxation) if and only if it is solvable on a certain distributed network, and this happens if and only if its set of Yes instances is closed under Weisfeiler-Leman equivalence. We generalize this result to the much broader framework of fixed-template Promise Valued Constraint Satisfaction Problems. Moreover, we show that two commonly used linear programming relaxations are no longer equivalent in this broader framework.
Cite as

Libor Barto and Silvia Butti. Weisfeiler-Leman Invariant Promise Valued CSPs. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barto_et_al:LIPIcs.CP.2022.4,
  author =	{Barto, Libor and Butti, Silvia},
  title =	{{Weisfeiler-Leman Invariant Promise Valued CSPs}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.4},
  URN =		{urn:nbn:de:0030-drops-166332},
  doi =		{10.4230/LIPIcs.CP.2022.4},
  annote =	{Keywords: Promise Valued Constraint Satisfaction Problem, Linear programming relaxation, Distributed algorithms, Symmetric fractional polymorphisms, Color refinement algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.11
Finitely Tractable Promise Constraint Satisfaction Problems

Authors: Kristina Asimi and Libor Barto

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP) that includes approximation variants of satisfiability and graph coloring problems. Barto [LICS '19] has shown that a specific PCSP, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP, but such a CSP is necessarily over an infinite domain (unless P=NP). We initiate a systematic study of this phenomenon by giving a general necessary condition for finite tractability and characterizing finite tractability within a class of templates - the "basic" tractable cases in the dichotomy theorem for symmetric Boolean PCSPs allowing negations by Brakensiek and Guruswami [SODA'18].
Cite as

Kristina Asimi and Libor Barto. Finitely Tractable Promise Constraint Satisfaction Problems. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{asimi_et_al:LIPIcs.MFCS.2021.11,
  author =	{Asimi, Kristina and Barto, Libor},
  title =	{{Finitely Tractable Promise Constraint Satisfaction Problems}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.11},
  URN =		{urn:nbn:de:0030-drops-144519},
  doi =		{10.4230/LIPIcs.MFCS.2021.11},
  annote =	{Keywords: Constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism, finite tractability, homomorphic relaxation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.10
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case

Authors: Libor Barto, Diego Battistelli, and Kevin M. Berg

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
The Promise Constraint Satisfaction Problem (PCSP) is a recently introduced vast generalization of the Constraint Satisfaction Problem (CSP). We investigate the computational complexity of a class of PCSPs beyond the most studied cases - approximation variants of satisfiability and graph coloring problems. We give an almost complete classification for the class of PCSPs of the form: given a 3-uniform hypergraph that has an admissible 2-coloring, find an admissible 3-coloring, where admissibility is given by a ternary symmetric relation. The only PCSP of this sort whose complexity is left open in this work is a natural hypergraph coloring problem, where admissibility is given by the relation "if two colors are equal, then the remaining one is higher."
Cite as

Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barto_et_al:LIPIcs.STACS.2021.10,
  author =	{Barto, Libor and Battistelli, Diego and Berg, Kevin M.},
  title =	{{Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.10},
  URN =		{urn:nbn:de:0030-drops-136557},
  doi =		{10.4230/LIPIcs.STACS.2021.10},
  annote =	{Keywords: constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.110
Sensitive Instances of the Constraint Satisfaction Problem

Authors: Libor Barto, Marcin Kozik, Johnson Tan, and Matt Valeriote

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

Abstract
We investigate the impact of modifying the constraining relations of a Constraint Satisfaction Problem (CSP) instance, with a fixed template, on the set of solutions of the instance. More precisely we investigate sensitive instances: an instance of the CSP is called sensitive, if removing any tuple from any constraining relation invalidates some solution of the instance. Equivalently, one could require that every tuple from any one of its constraints extends to a solution of the instance. Clearly, any non-trivial template has instances which are not sensitive. Therefore we follow the direction proposed (in the context of strict width) by Feder and Vardi in [Feder and Vardi, 1999] and require that only the instances produced by a local consistency checking algorithm are sensitive. In the language of the algebraic approach to the CSP we show that a finite idempotent algebra 𝔸 has a k+2 variable near unanimity term operation if and only if any instance that results from running the (k, k+1)-consistency algorithm on an instance over 𝔸² is sensitive. A version of our result, without idempotency but with the sensitivity condition holding in a variety of algebras, settles a question posed by G. Bergman about systems of projections of algebras that arise from some subalgebra of a finite product of algebras. Our results hold for infinite (albeit in the case of 𝔸 idempotent) algebras as well and exhibit a surprising similarity to the strict width k condition proposed by Feder and Vardi. Both conditions can be characterized by the existence of a near unanimity operation, but the arities of the operations differ by 1.
Cite as

Libor Barto, Marcin Kozik, Johnson Tan, and Matt Valeriote. Sensitive Instances of the Constraint Satisfaction Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 110:1-110:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barto_et_al:LIPIcs.ICALP.2020.110,
  author =	{Barto, Libor and Kozik, Marcin and Tan, Johnson and Valeriote, Matt},
  title =	{{Sensitive Instances of the Constraint Satisfaction Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{110:1--110:18},
  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.110},
  URN =		{urn:nbn:de:0030-drops-125176},
  doi =		{10.4230/LIPIcs.ICALP.2020.110},
  annote =	{Keywords: Constraint satisfaction problem, bounded width, local consistency, near unanimity operation, loop lemma}
}
Document
DOI: 10.4230/DFU.Vol7.15301.1
Polymorphisms, and How to Use Them

Authors: Libor Barto, Andrei Krokhin, and Ross Willard

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.
Cite as

Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 1-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{barto_et_al:DFU.Vol7.15301.1,
  author =	{Barto, Libor and Krokhin, Andrei and Willard, Ross},
  title =	{{Polymorphisms, and How to Use Them}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--44},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.1},
  URN =		{urn:nbn:de:0030-drops-69595},
  doi =		{10.4230/DFU.Vol7.15301.1},
  annote =	{Keywords: Constraint satisfaction, Complexity, Universal algebra, Polymorphism}
}
Document
DOI: 10.4230/DFU.Vol7.15301.45
Absorption in Universal Algebra and CSP

Authors: Libor Barto and Marcin Kozik

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
The algebraic approach to Constraint Satisfaction Problem led to many developments in both CSP and universal algebra. The notion of absorption was successfully applied on both sides of the connection. This article introduces the concept of absorption, illustrates its use in a number of basic proofs and provides an overview of the most important results obtained by using it.
Cite as

Libor Barto and Marcin Kozik. Absorption in Universal Algebra and CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 45-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{barto_et_al:DFU.Vol7.15301.45,
  author =	{Barto, Libor and Kozik, Marcin},
  title =	{{Absorption in Universal Algebra and CSP}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{45--77},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.45},
  URN =		{urn:nbn:de:0030-drops-69608},
  doi =		{10.4230/DFU.Vol7.15301.45},
  annote =	{Keywords: Constraint satisfaction problem, Algebraic approach, Absorption}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2016.2
Infinite Domain Constraint Satisfaction Problem (Invited Talk)

Authors: Libor Barto

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
The computational and descriptive complexity of finite domain fixed template constraint satisfaction problem (CSP) is a well developed topic that combines several areas in mathematics and computer science. Allowing the domain to be infinite provides a way larger playground which covers many more computational problems and requires further mathematical tools. I will talk about some of the research challenges and recent progress on them.
Cite as

Libor Barto. Infinite Domain Constraint Satisfaction Problem (Invited Talk). In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barto:LIPIcs.CSL.2016.2,
  author =	{Barto, Libor},
  title =	{{Infinite Domain Constraint Satisfaction Problem}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.2},
  URN =		{urn:nbn:de:0030-drops-65427},
  doi =		{10.4230/LIPIcs.CSL.2016.2},
  annote =	{Keywords: Descriptive complexity, Constraint Satisfaction Problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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