4 Search Results for "Tesson, Pascal"


Document
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Authors: Anup Rao and Amir Yehudayoff

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.

Cite as

Anup Rao and Amir Yehudayoff. Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 88-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{rao_et_al:LIPIcs.CCC.2015.88,
  author =	{Rao, Anup and Yehudayoff, Amir},
  title =	{{Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{88--101},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.88},
  URN =		{urn:nbn:de:0030-drops-50769},
  doi =		{10.4230/LIPIcs.CCC.2015.88},
  annote =	{Keywords: communication complexity, set disjointness, number on forehead, lower bounds}
}
Document
On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems

Authors: Carsten Lutz and Frank Wolter

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


Abstract
Recently, Fontaine has pointed out a connection between consistent query answering (CQA) and constraint satisfaction problems (CSP) [Fontaine, LICS 2013]. We investigate this connection more closely, identifying classes of CQA problems based on denial constraints and GAV constraints that correspond exactly to CSPs in the sense that a complexity classification of the CQA problems in each class is equivalent (up to FO-reductions) to classifying the complexity of all CSPs. We obtain these classes by admitting only monadic relations and only a single variable in denial constraints/GAVs and restricting queries to hypertree UCQs. We also observe that dropping the requirement of UCQs to be hypertrees corresponds to transitioning from CSP to its logical generalization MMSNP and identify a further relaxation that corresponds to transitioning from MMSNP to GMSNP (also know as MMSNP_2). Moreover, we use the CSP connection to carry over decidability of FO-rewritability and Datalog-rewritability to some of the identified classes of CQA problems.

Cite as

Carsten Lutz and Frank Wolter. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 363-379, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.ICDT.2015.363,
  author =	{Lutz, Carsten and Wolter, Frank},
  title =	{{On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{363--379},
  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.363},
  URN =		{urn:nbn:de:0030-drops-49958},
  doi =		{10.4230/LIPIcs.ICDT.2015.363},
  annote =	{Keywords: Consistent Query Answering, Constraint Satisfaction, Data Complexity, Dichotomies, Rewritability}
}
Document
Combinatorial Expressions and Lower Bounds

Authors: Thomas Colcombet and Amaldev Manuel

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
A new paradigm, called combinatorial expressions, for computing functions expressing properties over infinite domains is introduced. The main result is a generic technique, for showing indefinability of certain functions by the expressions, which uses a result, namely Hales-Jewett theorem, from Ramsey theory. An application of the technique for proving inexpressibility results for logics on metafinite structures is given. Some extensions and normal forms are also presented.

Cite as

Thomas Colcombet and Amaldev Manuel. Combinatorial Expressions and Lower Bounds. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{colcombet_et_al:LIPIcs.STACS.2015.249,
  author =	{Colcombet, Thomas and Manuel, Amaldev},
  title =	{{Combinatorial Expressions and Lower Bounds}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{249--261},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.249},
  URN =		{urn:nbn:de:0030-drops-49181},
  doi =		{10.4230/LIPIcs.STACS.2015.249},
  annote =	{Keywords: expressions, lower bound, indefinability}
}
Document
The Complexity of the List Homomorphism Problem for Graphs

Authors: László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
We completely classify the computational complexity of the list $\bH$-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph $\bH$ the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.

Cite as

László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson. The Complexity of the List Homomorphism Problem for Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 335-346, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{egri_et_al:LIPIcs.STACS.2010.2467,
  author =	{Egri, L\'{a}szl\'{o} and Krokhin, Andrei and Larose, Benoit and Tesson, Pascal},
  title =	{{The Complexity of the List Homomorphism Problem for Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{335--346},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2467},
  URN =		{urn:nbn:de:0030-drops-24675},
  doi =		{10.4230/LIPIcs.STACS.2010.2467},
  annote =	{Keywords: Graph homomorphism, constraint satisfaction problem, complexity, universal algebra, Datalog}
}
  • Refine by Author
  • 1 Colcombet, Thomas
  • 1 Egri, László
  • 1 Krokhin, Andrei
  • 1 Larose, Benoit
  • 1 Lutz, Carsten
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Consistent Query Answering
  • 1 Constraint Satisfaction
  • 1 Data Complexity
  • 1 Datalog
  • 1 Dichotomies
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 2015
  • 1 2010

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