Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Cai, Jin-Yi Lu, Pinyan Xia, Mingji dblp dblp dblp Not MPG Author(s): Cai, Jin-Yi Lu, Pinyan
 Editor(s):
 BibTeX cite key*: Xia2013-soda-clx

 Title, Booktitle
 Title*: Dichotomy for Holant* Problems with a Function on Domain Size 3 Booktitle*: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da13/ URL for downloading the paper: Event Address*: New Orleans, Louisiana USA Language: English Event Date* (no longer used): Organization: Event Start Date: 6 January 2013 Event End Date: 8 January 2013

 Publisher

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: Pages: 1278-1295 Year*: 2013 VG Wort Pages: ISBN/ISSN: 978-1-611972-52-8 Sequence Number: DOI:

 (LaTeX) Abstract: Holant problems are a general framework to study the algorithmic complexity of counting problems. Both counting constraint satisfaction problems and graph homomorphisms are special cases. All previous results of Holant problems are over the Boolean domain. In this paper, we give the first dichotomy theorem for Holant problems for domain size greater than two. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size greater than two. This is our main algorithmic technique, and is used for both tractable families and hardness reductions. The dichotomy theorem is the following: For any complex-valued symmetric function ${\bf F}$ with arity 3 on domain size 3, we give an explicit criterion on ${\bf F}$, such that if ${\bf F}$ satisfies the criterion then the problem ${\rm Holant}^*({\bf F})$ is computable in polynomial time, otherwise ${\rm Holant}^*({\bf F})$ is \#P-hard. Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Xia2013-soda-clx,
AUTHOR = {Cai, Jin-Yi and Lu, Pinyan and Xia, Mingji},
TITLE = {Dichotomy for {Holant*} Problems with a Function on Domain Size 3},
BOOKTITLE = {Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms},
PUBLISHER = {SIAM},
YEAR = {2013},
PAGES = {1278--1295},
ADDRESS = {New Orleans, Louisiana USA},
ISBN = {978-1-611972-52-8},
}