Search Results

Documents authored by Bulatov, Andrei

Found 2 Possible Name Variants:

Bulatov, Andrei A.

Document
DOI: 10.4230/LIPIcs.STACS.2022.18
The Ideal Membership Problem and Abelian Groups

Authors: Andrei A. Bulatov and Akbar Rafiey

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Given polynomials f_0, f_1, …, f_k the Ideal Membership Problem, IMP for short, asks if f₀ belongs to the ideal generated by f_1, …, f_k. In the search version of this problem the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications, for instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved. Mastrolilli [SODA'19] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(Γ). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(Γ) where Γ is a Boolean constraint language, while Bulatov and Rafiey [arXiv'21] advanced these results to several cases of CSPs over finite domains. In this paper we consider IMPs arising from CSPs over "affine" constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS'21] for linear equation modulo 2, and by Bulatov and Rafiey [arXiv'21] to systems of linear equations over GF(p), p prime. Here we prove that if Γ is an affine constraint language then IMP(Γ) is solvable in polynomial time assuming the input polynomial has bounded degree.
Cite as

Andrei A. Bulatov and Akbar Rafiey. The Ideal Membership Problem and Abelian Groups. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2022.18,
  author =	{Bulatov, Andrei A. and Rafiey, Akbar},
  title =	{{The Ideal Membership Problem and Abelian Groups}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra 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.2022.18},
  URN =		{urn:nbn:de:0030-drops-158280},
  doi =		{10.4230/LIPIcs.STACS.2022.18},
  annote =	{Keywords: Polynomial Ideal Membership, Constraint Satisfaction Problems, Polymorphisms, Gr\"{o}bner Bases, Abelian Groups}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2021.2
Symmetries and Complexity (Invited Talk)

Authors: Andrei A. Bulatov

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The Constraint Satisfaction Problem (CSP) and a number of problems related to it have seen major advances during the past three decades. In many cases the leading driving force that made these advances possible has been the so-called algebraic approach that uses symmetries of constraint problems and tools from algebra to determine the complexity of problems and design solution algorithms. In this presentation we give a high level overview of the main ideas behind the algebraic approach illustrated by examples ranging from the regular CSP, to counting problems, to optimization and promise problems, to graph isomorphism.
Cite as

Andrei A. Bulatov. Symmetries and Complexity (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bulatov:LIPIcs.ICALP.2021.2,
  author =	{Bulatov, Andrei A.},
  title =	{{Symmetries and Complexity}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.2},
  URN =		{urn:nbn:de:0030-drops-140717},
  doi =		{10.4230/LIPIcs.ICALP.2021.2},
  annote =	{Keywords: constraint problems, algebraic approach, dichotomy theorems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.21
Counting Homomorphisms in Plain Exponential Time

Authors: Andrei A. Bulatov and Amineh Dadsetan

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

Abstract
In the counting Graph Homomorphism problem (#GraphHom) the question is: Given graphs G,H, find the number of homomorphisms from G to H. This problem is generally #P-complete, moreover, Cygan et al. proved that unless the Exponential Time Hypothesis fails there is no algorithm that solves this problem in time O(|V(H)|^o(|V(G)|)). This, however, does not rule out the possibility that faster algorithms exist for restricted problems of this kind. Wahlström proved that #GraphHom can be solved in plain exponential time, that is, in time O((2k+1)^(|V(G)|+|V(H)|) poly(|V(H)|,|V(G)|)) provided H has clique width k. We generalize this result to a larger class of graphs, and also identify several other graph classes that admit a plain exponential algorithm for #GraphHom.
Cite as

Andrei A. Bulatov and Amineh Dadsetan. Counting Homomorphisms in Plain Exponential Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.ICALP.2020.21,
  author =	{Bulatov, Andrei A. and Dadsetan, Amineh},
  title =	{{Counting Homomorphisms in Plain Exponential Time}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-124287},
  doi =		{10.4230/LIPIcs.ICALP.2020.21},
  annote =	{Keywords: graph homomorphisms, plain exponential time, clique width}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.59
Counting Homomorphisms Modulo a Prime Number

Authors: Amirhossein Kazeminia and Andrei A. Bulatov

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Counting problems in general and counting graph homomorphisms in particular have numerous applications in combinatorics, computer science, statistical physics, and elsewhere. One of the most well studied problems in this area is #GraphHom(H) - the problem of finding the number of homomorphisms from a given graph G to the graph H. Not only the complexity of this basic problem is known, but also of its many variants for digraphs, more general relational structures, graphs with weights, and others. In this paper we consider a modification of #GraphHom(H), the #_{p}GraphHom(H) problem, p a prime number: Given a graph G, find the number of homomorphisms from G to H modulo p. In a series of papers Faben and Jerrum, and Göbel et al. determined the complexity of #_{2}GraphHom(H) in the case H (or, in fact, a certain graph derived from H) is square-free, that is, does not contain a 4-cycle. Also, Göbel et al. found the complexity of #_{p}GraphHom(H) when H is a tree for an arbitrary prime p. Here we extend the above result to show that the #_{p}GraphHom(H) problem is #_{p}P-hard whenever the derived graph associated with H is square-free and is not a star, which completely classifies the complexity of #_{p}GraphHom(H) for square-free graphs H.
Cite as

Amirhossein Kazeminia and Andrei A. Bulatov. Counting Homomorphisms Modulo a Prime Number. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kazeminia_et_al:LIPIcs.MFCS.2019.59,
  author =	{Kazeminia, Amirhossein and Bulatov, Andrei A.},
  title =	{{Counting Homomorphisms Modulo a Prime Number}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar 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.MFCS.2019.59},
  URN =		{urn:nbn:de:0030-drops-110032},
  doi =		{10.4230/LIPIcs.MFCS.2019.59},
  annote =	{Keywords: graph homomorphism, modular counting, computational hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.60
Approximate Counting CSP Seen from the Other Side

Authors: Andrei A. Bulatov and Stanislav Živný

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that #CSP(C,-) is solvable in polynomial time if C has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if C is a recursively enumerable class of relational structures of bounded arity, then assuming FPT != #W[1], there are no other cases of #CSP(C,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT != W[1] (under randomised parametrised reductions) and for C satisfying certain general conditions, #CSP(C,-) is not solvable even approximately for C of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(C,-). In particular, our condition generalises the case when C is closed under taking minors.
Cite as

Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.MFCS.2019.60,
  author =	{Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Approximate Counting CSP Seen from the Other Side}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{60:1--60:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar 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.MFCS.2019.60},
  URN =		{urn:nbn:de:0030-drops-110041},
  doi =		{10.4230/LIPIcs.MFCS.2019.60},
  annote =	{Keywords: constraint satisfaction, approximate counting, homomorphisms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.29
Dismantlability, Connectedness, and Mixing in Relational Structures

Authors: Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, and Benoît Larose

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, statistical physics, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, topological properties of the solution set such as connectedness is related to the hardness of CSPs over random structures. In approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions or the free energy of spin systems. Additionally, in the decision CSPs, structural properties of the relational structures involved - like, for example, dismantlability - and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that the structural property of dismantlability of the target graph, the connectedness of the set of homomorphisms, good mixing properties of the corresponding spin system, and the uniqueness of Gibbs measure are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Briceño. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.
Cite as

Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, and Benoît Larose. Dismantlability, Connectedness, and Mixing in Relational Structures. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{briceno_et_al:LIPIcs.ICALP.2019.29,
  author =	{Brice\~{n}o, Raimundo and Bulatov, Andrei A. and Dalmau, V{\'\i}ctor and Larose, Beno\^{i}t},
  title =	{{Dismantlability, Connectedness, and Mixing in Relational Structures}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.29},
  URN =		{urn:nbn:de:0030-drops-106059},
  doi =		{10.4230/LIPIcs.ICALP.2019.29},
  annote =	{Keywords: relational structure, constraint satisfaction problem, homomorphism, mixing properties, Gibbs measure}
}
Document
DOI: 10.4230/DagRep.5.7.22
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)

Authors: Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx

Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)

Abstract
During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, mathematical programming, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. This research direction develops at an impressive speed, regularly producing very strong and general results. The Dagstuhl Seminar 15301 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights obtained during the past three years. This report documents the material presented during the course of the seminar.
Cite as

Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{bulatov_et_al:DagRep.5.7.22,
  author =	{Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}},
  pages =	{22--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{7},
  editor =	{Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.7.22},
  URN =		{urn:nbn:de:0030-drops-56714},
  doi =		{10.4230/DagRep.5.7.22},
  annote =	{Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.302
Log-supermodular functions, functional clones and counting CSPs

Authors: Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that non-negative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard as any problem in #P. Furthermore, any non-trivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all non-trivial counting CSPs (with non-negative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately.
Cite as

Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 302-313, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2012.302,
  author =	{Bulatov, Andrei A. and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{Log-supermodular functions, functional clones and counting CSPs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{302--313},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.302},
  URN =		{urn:nbn:de:0030-drops-34078},
  doi =		{10.4230/LIPIcs.STACS.2012.302},
  annote =	{Keywords: counting constraint satisfaction problems, approximation, complexity}
}
Document
DOI: 10.4230/DagSemProc.09441.1
09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability

Authors: Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
From 25th to 30th October 2009, the Dagstuhl Seminar 09441 ``The Constraint Satisfaction Problem: Complexity and Approximability'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin. 09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:DagSemProc.09441.1,
  author =	{Bulatov, Andrei A. and Grohe, Martin and Kolaitis, Phokion G. and Krokhin, Andrei},
  title =	{{09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.1},
  URN =		{urn:nbn:de:0030-drops-23710},
  doi =		{10.4230/DagSemProc.09441.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP), satisfiability, computational complexity, CSP dichotomy conjecture, hardness of approximation, unique games conjecture, universal algebra, logic}
}
Document
DOI: 10.4230/DagSemProc.09441.2
09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability

Authors: Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
The seminar brought together forty researchers from di®erent highly advanced areas of constraint satisfaction and with complementary ex- pertise (logical, algebraic, combinatorial, probabilistic aspects). The list of participants contained both senior and junior researchers and a small number of advanced graduate students.
Cite as

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin. 09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:DagSemProc.09441.2,
  author =	{Bulatov, Andrei A. and Grohe, Martin and Kolaitis, Phokion G. and Krokhin, Andrei},
  title =	{{09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.2},
  URN =		{urn:nbn:de:0030-drops-23706},
  doi =		{10.4230/DagSemProc.09441.2},
  annote =	{Keywords: Constraint satisfaction problem (CSP), satisfiability, computational complexity, CSP dichotomy conjecture, hardness of approximation, unique games conjecture, universal algebra, logic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1838
Enumerating Homomorphisms

Authors: Andrei A. Bulatov, Victor Dalmau, Martin Grohe, and Daniel Marx

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.
Cite as

Andrei A. Bulatov, Victor Dalmau, Martin Grohe, and Daniel Marx. Enumerating Homomorphisms. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 231-242, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2009.1838,
  author =	{Bulatov, Andrei A. and Dalmau, Victor and Grohe, Martin and Marx, Daniel},
  title =	{{Enumerating Homomorphisms}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{231--242},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1838},
  URN =		{urn:nbn:de:0030-drops-18385},
  doi =		{10.4230/LIPIcs.STACS.2009.1838},
  annote =	{Keywords: }
}

Bulatov, Andrei

Document
DOI: 10.4230/LIPIcs.CSL.2013.149
Descriptive complexity of approximate counting CSPs

Authors: Andrei Bulatov, Victor Dalmau, and Marc Thurley

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract
Motivated by Fagin's characterization of NP, Saluja et al. have introduced a logic based frame- work for expressing counting problems. In this setting, a counting problem (seen as a mapping C from structures to non-negative integers) is `defined’ by a first-order sentence phi if for every instance A of the problem, the number of possible satisfying assignments of the variables of phi in A is equal to C(A). The logic RHPI_1 has been introduced by Dyer et al. in their study of the counting complexity class #BIS. The interest in the class #BIS stems from the fact that, it is quite plausible that the problems in #BIS are not #P-hard, nor they admit a fully polynomial randomized approximation scheme. In the present paper we investigate which counting constraint satisfaction problems #CSP(H) are definable in the monotone fragment of RHPI_1. We prove that #CSP(H) is definable in monotone RHPI_1 whenever H is invariant under meet and join operations of a distributive lattice. We prove that the converse also holds if H contains the equality relation. We also prove similar results for counting CSPs expressible by linear Datalog. The results in this case are very similar to those for monotone RHPI1, with the addition that H has, additionally, \top (the greatest element of the lattice) as a polymorphism.
Cite as

Andrei Bulatov, Victor Dalmau, and Marc Thurley. Descriptive complexity of approximate counting CSPs. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 149-164, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.CSL.2013.149,
  author =	{Bulatov, Andrei and Dalmau, Victor and Thurley, Marc},
  title =	{{Descriptive complexity of approximate counting CSPs}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{149--164},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.149},
  URN =		{urn:nbn:de:0030-drops-41955},
  doi =		{10.4230/LIPIcs.CSL.2013.149},
  annote =	{Keywords: Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity}
}
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 About DROPS Imprint Privacy Contact