License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.40
URN: urn:nbn:de:0030-drops-135793
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13579/
Go to the corresponding LIPIcs Volume Portal

Lin, Jiabao

On the Complexity of #CSP^d

pdf-format:
LIPIcs-ITCS-2021-40.pdf (0.5 MB)

Abstract

Counting CSP^d is the counting constraint satisfaction problem (#CSP in short) restricted to the instances where every variable occurs a multiple of d times. This paper revisits tractable structures in #CSP and gives a complexity classification theorem for #CSP^d with algebraic complex weights. The result unifies affine functions (stabilizer states in quantum information theory) and related variants such as the local affine functions, the discovery of which leads to all the recent progress on the complexity of Holant problems.
The Holant is a framework that generalizes counting CSP. In the literature on Holant problems, weighted constraints are often expressed as tensors (vectors) such that projections and linear transformations help analyze the structure. This paper gives an example showing that different classes of tensors distinguished by these algebraic operations may share the same closure property under tensor product and contraction.

BibTeX - Entry

@InProceedings{lin:LIPIcs.ITCS.2021.40,
  author =	{Jiabao Lin},
  title =	{{On the Complexity of #CSP^d}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{40:1--40:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13579},
  URN =		{urn:nbn:de:0030-drops-135793},
  doi =		{10.4230/LIPIcs.ITCS.2021.40},
  annote =	{Keywords: Constraint satisfaction problem, counting problems, Holant, complexity dichotomy}
}

Keywords: Constraint satisfaction problem, counting problems, Holant, complexity dichotomy
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI