17 Search Results for "Creignou, Nadia"


Document
Enumeration Classes Defined by Circuits

Authors: Nadia Creignou, Arnaud Durand, and Heribert Vollmer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.

Cite as

Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38,
  author =	{Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert},
  title =	{{Enumeration Classes Defined by Circuits}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-168364},
  doi =		{10.4230/LIPIcs.MFCS.2022.38},
  annote =	{Keywords: Computational complexity, enumeration problem, Boolean circuit}
}
Document
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
A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties

Authors: Karl Bringmann, Nick Fischer, and Marvin Künnemann

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
An important class of problems in logics and database theory is given by fixing a first-order property psi over a relational structure, and considering the model-checking problem for psi. Recently, Gao, Impagliazzo, Kolokolova, and Williams (SODA 2017) identified this class as fundamental for the theory of fine-grained complexity in P, by showing that the (Sparse) Orthogonal Vectors problem is complete for this class under fine-grained reductions. This raises the question whether fine-grained complexity can yield a precise understanding of all first-order model-checking problems. Specifically, can we determine, for any fixed first-order property psi, the exponent of the optimal running time O(m^{c_psi}), where m denotes the number of tuples in the relational structure? Towards answering this question, in this work we give a dichotomy for the class of exists^k-forall-quantified graph properties. For every such property psi, we either give a polynomial-time improvement over the baseline O(m^k)-time algorithm or show that it requires time m^{k-o(1)} under the hypothesis that MAX-3-SAT has no O((2-epsilon)^n)-time algorithm. More precisely, we define a hardness parameter h = H(psi) such that psi can be decided in time O(m^{k-epsilon}) if h <=2 and requires time m^{k-o(1)} for h >= 3 unless the h-uniform HyperClique hypothesis fails. This unveils a natural hardness hierarchy within first-order properties: for any h >= 3, we show that there exists a exists^k-forall-quantified graph property psi with hardness H(psi)=h that is solvable in time O(m^{k-epsilon}) if and only if the h-uniform HyperClique hypothesis fails. Finally, we give more precise upper and lower bounds for an exemplary class of formulas with k=3 and extend our classification to a counting dichotomy.

Cite as

Karl Bringmann, Nick Fischer, and Marvin Künnemann. A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 31:1-31:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.CCC.2019.31,
  author =	{Bringmann, Karl and Fischer, Nick and K\"{u}nnemann, Marvin},
  title =	{{A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{31:1--31:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.31},
  URN =		{urn:nbn:de:0030-drops-108533},
  doi =		{10.4230/LIPIcs.CCC.2019.31},
  annote =	{Keywords: Fine-grained Complexity, Hardness in P, Hyperclique Conjecture, Constrained Triangle Detection}
}
Document
SAT and Interactions (Dagstuhl Seminar 16381)

Authors: Olaf Beyersdorff, Nadia Creignou, Uwe Egly, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)


Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 16381 "SAT and Interactions". The seminar brought together researchers from different areas from theoretical computer science involved with various aspects of satisfiability. A key objective of the seminar has been to initiate or consolidate discussions among the different groups for a fresh attack on one of the most important problems in theoretical computer science and mathematics.

Cite as

Olaf Beyersdorff, Nadia Creignou, Uwe Egly, and Heribert Vollmer. SAT and Interactions (Dagstuhl Seminar 16381). In Dagstuhl Reports, Volume 6, Issue 9, pp. 74-93, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{beyersdorff_et_al:DagRep.6.9.74,
  author =	{Beyersdorff, Olaf and Creignou, Nadia and Egly, Uwe and Vollmer, Heribert},
  title =	{{SAT and Interactions (Dagstuhl Seminar 16381)}},
  pages =	{74--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{9},
  editor =	{Beyersdorff, Olaf and Creignou, Nadia and Egly, Uwe and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.9.74},
  URN =		{urn:nbn:de:0030-drops-69116},
  doi =		{10.4230/DagRep.6.9.74},
  annote =	{Keywords: Combinatorics, Computational Complexity, P vs. NP, Proof Complexity, Quantified Boolean formulas, SAT-solvers, satisfiability problem}
}
Document
Complexity and Approximability of Parameterized MAX-CSPs

Authors: Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable–constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k. We attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT-time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPT-AS), which computes a (1-epsilon)-approximation in time f(k,epsilon) * poly(n). 3. There is no FPT-AS unless FPT=W[1]. For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.

Cite as

Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294,
  author =	{Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias},
  title =	{{Complexity and Approximability of Parameterized MAX-CSPs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{294--306},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294},
  URN =		{urn:nbn:de:0030-drops-55910},
  doi =		{10.4230/LIPIcs.IPEC.2015.294},
  annote =	{Keywords: Approximation, Structural Parameters, Constraint Satisfaction}
}
Document
The Product Homomorphism Problem and Applications

Authors: Balder ten Cate and Victor Dalmau

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)


Abstract
The product homomorphism problem (PHP) takes as input a finite collection of structures A_1, ..., A_n and a structure B, and asks if there is a homomorphism from the direct product between A_1, A_2, ..., and A_n, to B. We pinpoint the computational complexity of this problem. Our motivation stems from the fact that PHP naturally arises in different areas of database theory. In particular, it is equivalent to the problem of determining whether a relation is definable by a conjunctive query, and the existence of a schema mapping that fits a given collection of positive and negative data examples. We apply our results to obtain complexity bounds for these problems.

Cite as

Balder ten Cate and Victor Dalmau. The Product Homomorphism Problem and Applications. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 161-176, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.ICDT.2015.161,
  author =	{ten Cate, Balder and Dalmau, Victor},
  title =	{{The Product Homomorphism Problem and Applications}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{161--176},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.161},
  URN =		{urn:nbn:de:0030-drops-49832},
  doi =		{10.4230/LIPIcs.ICDT.2015.161},
  annote =	{Keywords: Homomorphisms, Direct Product, Data Examples, Definability, Conjunctive Queries, Schema Mappings}
}
Document
Robust Approximation of Temporal CSP

Authors: Suguru Tamaki and Yuichi Yoshida

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


Abstract
A temporal constraint language G is a set of relations with first-order definitions in (Q; <). Let CSP(G) denote the set of constraint satisfaction problem instances with relations from G. CSP(G) admits robust approximation if, for any e >= 0, given a (1-e)-satisfiable instance of CSP(G), we can compute an assignment that satisfies at least a (1-f(e))-fraction of constraints in polynomial time. Here, f(e) is some function satisfying f(0)=0 and f(e) goes 0 as e goes 0. Firstly, we give a qualitative characterization of robust approximability: Assuming the Unique Games Conjecture, we give a necessary and sufficient condition on G under which CSP(G) admits robust approximation. Secondly, we give a quantitative characterization of robust approximability: Assuming the Unique Games Conjecture, we precisely characterize how f(e) depends on e for each G. We show that our robust approximation algorithms can be run in almost linear time.

Cite as

Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 419-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{tamaki_et_al:LIPIcs.APPROX-RANDOM.2014.419,
  author =	{Tamaki, Suguru and Yoshida, Yuichi},
  title =	{{Robust Approximation of Temporal CSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{419--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.419},
  URN =		{urn:nbn:de:0030-drops-47135},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.419},
  annote =	{Keywords: constraint satisfaction, maximum satisfiability, approximation algorithm, hardness of approximation, infinite domain}
}
Document
Universal Factor Graphs for Every NP-Hard Boolean CSP

Authors: Shlomo Jozeph

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


Abstract
An instance of a Boolean constraint satisfaction problem can be divided into two parts. One part, that we refer to as the factor graph of the instance, specifies for each clause the set of variables that are associated with the clause. The other part, specifies for each of the given clauses what is the constraint that is evaluated on the respective variables. Depending on the allowed choices of constraints, it is known that Boolean constraint satisfaction problems fall into one of two classes, being either NP-hard or in P. This paper shows that every NP-hard Boolean constraint satisfaction problem (except for an easy to characterize set of natural exceptions) has a universal factor graph. That is, for every NP-hard Boolean constraint satisfaction problem, there is a family of at most one factor graph of each size, such that the problem, restricted to instances that have a factor graph from this family, cannot be solved in polynomial time unless NP is contained in P/poly. Moreover, we extend this classification to one that establishes hardness of approximation.

Cite as

Shlomo Jozeph. Universal Factor Graphs for Every NP-Hard Boolean CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 274-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{jozeph:LIPIcs.APPROX-RANDOM.2014.274,
  author =	{Jozeph, Shlomo},
  title =	{{Universal Factor Graphs for Every NP-Hard Boolean CSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{274--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.274},
  URN =		{urn:nbn:de:0030-drops-47021},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.274},
  annote =	{Keywords: Hardness of Approximation, Hardness with Preprocessing}
}
Document
SAT Interactions (Dagstuhl Seminar 12471)

Authors: Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)


Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 12471 "SAT Interactions". The seminar brought together researchers from different areas from theoretical computer science as well as the area of SAT solvers. A key objective of the seminar has been to initiate or consolidate discussions among the different groups for a fresh attack on one of the most important problems in theoretical computer science and mathematics.

Cite as

Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer. SAT Interactions (Dagstuhl Seminar 12471). In Dagstuhl Reports, Volume 2, Issue 11, pp. 87-101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{creignou_et_al:DagRep.2.11.87,
  author =	{Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert},
  title =	{{SAT Interactions (Dagstuhl Seminar 12471)}},
  pages =	{87--101},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.87},
  URN =		{urn:nbn:de:0030-drops-39786},
  doi =		{10.4230/DagRep.2.11.87},
  annote =	{Keywords: satisfiability problem, computational complexity, P-NP question, proof complexity, combinatorics, SAT-solvers, quantified Boolean formulas}
}
Document
The Complexity of Reasoning for Fragments of Autoepistemic Logic

Authors: Nadia Creignou, Arne Meier, Michael Thomas, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)


Abstract
Autoepistemic logic extends propositional logic by the modal operator L. A formula that is preceded by an L is said to be "believed". The logic was introduced by Moore 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for autoepistemic logic.

Cite as

Nadia Creignou, Arne Meier, Michael Thomas, and Heribert Vollmer. The Complexity of Reasoning for Fragments of Autoepistemic Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{creignou_et_al:DagSemProc.10061.6,
  author =	{Creignou, Nadia and Meier, Arne and Thomas, Michael and Vollmer, Heribert},
  title =	{{The Complexity of Reasoning for Fragments of Autoepistemic Logic}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.6},
  URN =		{urn:nbn:de:0030-drops-25234},
  doi =		{10.4230/DagSemProc.10061.6},
  annote =	{Keywords: Autoepistemic logic, computational complexity, nonmonotonic reasoning, Post's lattice}
}
Document
06401 Abstracts Collection – Complexity of Constraints

Authors: Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)


Abstract
From 01.10.06 to 06.10.06, the Dagstuhl Seminar 06401 ``Complexity of Constraints'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. 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

Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer. 06401 Abstracts Collection – Complexity of Constraints. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{creignou_et_al:DagSemProc.06401.1,
  author =	{Creignou, Nadia and Kolaitis, Phokion and Vollmer, Heribert},
  title =	{{06401 Abstracts Collection – Complexity of Constraints}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.1},
  URN =		{urn:nbn:de:0030-drops-8067},
  doi =		{10.4230/DagSemProc.06401.1},
  annote =	{Keywords: Constraint satisfaction problems, computational complexity, universal algebra, mathematical logic, finite model theory}
}
Document
06401 Executive Summary – Complexity of Constraints

Authors: Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)


Abstract
In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.

Cite as

Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer. 06401 Executive Summary – Complexity of Constraints. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{creignou_et_al:DagSemProc.06401.2,
  author =	{Creignou, Nadia and Kolaitis, Phokion and Vollmer, Heribert},
  title =	{{06401 Executive Summary – Complexity of Constraints}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.2},
  URN =		{urn:nbn:de:0030-drops-8001},
  doi =		{10.4230/DagSemProc.06401.2},
  annote =	{Keywords: Constraint satisfaction problems, complexity}
}
Document
A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

Authors: David Cohen, Marc Gyssens, and Peter Jeavons

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)


Abstract
In this talk (draft paper) we develop the theory of structural decompositions for the CSP. We begin with the very general notion of a guarded decomposition and make several simplifying assumptions to arrive a the definition of an acyclic guarded cover. We show how many existing decompositions can seen as acyclic guarded covers. We develop a generic algorithm for discovering acyclic guarded covers under the further assumption that they have a join tree satisfying a simple extra condition. We show that many existing decompositions do in fact satisfy this extra condition. Using this theory we are able to describe a new class of structural decompostion which we call spread cuts. These generalise many existing decomposition methods. We present a class of hypergraphs whose spread cut width is significantly smaller than their hypertree width. The definition of a guarded decomposition and the algorithm for discovering them were motvated by the similar algorithms developed by Gottlob, Scarcello and Leone in their work on hypertrees. The authors also wish to acknowledge that an acyclic guarded decomposition is very similar to a generalised hypertree decomposition as described in the hypertree literature.

Cite as

David Cohen, Marc Gyssens, and Peter Jeavons. A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:DagSemProc.06401.3,
  author =	{Cohen, David and Gyssens, Marc and Jeavons, Peter},
  title =	{{A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.3},
  URN =		{urn:nbn:de:0030-drops-8017},
  doi =		{10.4230/DagSemProc.06401.3},
  annote =	{Keywords: Structural decomposition, spread cut}
}
Document
Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities

Authors: Oliver Kullmann

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)


Abstract
Generalised CNFs are considered using such literals, which exclude exactly one possible value from the domain of the variable. First we consider poly-time SAT decision (and fixed-parameter tractability) exploiting matching theory. Then we consider irredundant generalised CNFs, and characterise some extremal minimally unsatisfiable CNFs.

Cite as

Oliver Kullmann. Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{kullmann:DagSemProc.06401.4,
  author =	{Kullmann, Oliver},
  title =	{{Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities}},
  booktitle =	{Complexity of Constraints},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.4},
  URN =		{urn:nbn:de:0030-drops-8030},
  doi =		{10.4230/DagSemProc.06401.4},
  annote =	{Keywords: Signed CNF, autarkies, minimal unsatisfiable, hypergraph colouring, block designs}
}
Document
Constraint Satisfaction with Succinctly Specified Relations

Authors: Hubie Chen and Martin Grohe

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)


Abstract
The general intractability of the constraint satisfaction problem has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations. This is joint work with Hubie Chen.

Cite as

Hubie Chen and Martin Grohe. Constraint Satisfaction with Succinctly Specified Relations. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.06401.5,
  author =	{Chen, Hubie and Grohe, Martin},
  title =	{{Constraint Satisfaction with Succinctly Specified Relations}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.5},
  URN =		{urn:nbn:de:0030-drops-8022},
  doi =		{10.4230/DagSemProc.06401.5},
  annote =	{Keywords: Constraint satisfaction, complexity, succinct representations}
}
  • Refine by Author
  • 6 Creignou, Nadia
  • 6 Vollmer, Heribert
  • 2 Kolaitis, Phokion
  • 2 Kullmann, Oliver
  • 2 Schnoor, Henning
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 3 computational complexity
  • 3 constraint satisfaction
  • 2 Constraint satisfaction problems
  • 2 SAT-solvers
  • 2 complexity
  • Show More...

  • Refine by Type
  • 17 document

  • Refine by Publication Year
  • 7 2006
  • 2 2014
  • 2 2015
  • 2 2019
  • 1 2010
  • Show More...

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