1 Search Results for "Wang, Hanpin"


Document
The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Authors: Jiabao Lin and Hanpin Wang

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over the Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice #CSPs. Intuitively, some #CSPs that are #P-hard become tractable when restricted to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set F satisfies the condition, then F is of affine type or product type. Otherwise (a) Holant(F) is #P-hard; or (b) every function in F is a tensor product of functions of arity at most 2; or (c) F is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.

Cite as

Jiabao Lin and Hanpin Wang. The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ICALP.2017.29,
  author =	{Lin, Jiabao and Wang, Hanpin},
  title =	{{The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.29},
  URN =		{urn:nbn:de:0030-drops-73846},
  doi =		{10.4230/LIPIcs.ICALP.2017.29},
  annote =	{Keywords: counting complexity, dichotomy, Holant, #CSP}
}
  • Refine by Author
  • 1 Lin, Jiabao
  • 1 Wang, Hanpin

  • Refine by Classification

  • Refine by Keyword
  • 1 #CSP
  • 1 Holant
  • 1 counting complexity
  • 1 dichotomy

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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