NDLI: From Holant to #CSP and Back: Dichotomy for Holant c Problems

Content Provider	Springer Nature Link
Author	Cai, Jin Yi Huang, Sangxia Lu, Pinyan
Copyright Year	2012
Abstract	We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain ℂ. We prove three complexity dichotomy theorems, leading to a general theorem for Holant c problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on G=(V,E) over a set of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to , of $$\sum_{\sigma: E \rightarrow \{0,1\}}\prod_{v\in V} f_v(\sigma \vert _{E(v)}),$$ where (0, 1 are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy can be only naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on Boolean complex weighted #CSP.
Starting Page	511
Ending Page	533
Page Count	23
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	64
Issue Number	3
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-03-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Holant problem #CSP Holographic reduction Dichotomy Theory of Computation Algorithm Analysis and Problem Complexity Algorithms Data Structures, Cryptology and Information Theory Mathematics of Computing Computer Systems Organization and Communication Networks
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Signature Theory in Holographic Algorithms

A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP

Erratum to: Signature Theory in Holographic Algorithms

Sample Complexity for Computational Classification Problems

Scalable Parallel Algorithms for FPT Problems

Approximating Satisfiable Satisfiability Problems

The Relative Complexity of Approximate Counting Problems

Reallocation Problems in Scheduling

Primal–Dual Algorithms for Connected Facility Location Problems

From Holant to #CSP and Back: Dichotomy for Holant c Problems

Similar Documents

Signature Theory in Holographic Algorithms

A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP

Erratum to: Signature Theory in Holographic Algorithms

Sample Complexity for Computational Classification Problems

Scalable Parallel Algorithms for FPT Problems

Approximating Satisfiable Satisfiability Problems

The Relative Complexity of Approximate Counting Problems

Reallocation Problems in Scheduling

Primal–Dual Algorithms for Connected Facility Location Problems

From Holant to #CSP and Back: Dichotomy for Holant c Problems