Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

Name*:

SIAM

URL:


Address*:

Philadelphia, PA

Type:


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:




Note, Abstract, ©


(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},
}


Entry last modified by Anja Becker, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/05/2013 08:08:59 AM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Stephanie Müller
Stephanie Müller
Mengji Xia
Mengji Xia
Edit Dates
06.02.2013 09:48:57
05.02.2013 08:15:00
05.02.2013 08:08:47
2012-11-26 16:42:45
2012-11-26 16:22:01