A Computational Proof of Complexity of Some Restricted Counting Problems

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Type: Book-Chapter

Publication Date: 2009-01-01

Citations: 14

DOI: https://doi.org/10.1007/978-3-642-02017-9_17

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	A computational proof of complexity of some restricted counting problems	2010	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Computational Complexity of Holant Problems	2011	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Dichotomy for Holant* Problems with a Function on Domain Size 3	2012	Jin‐Yi Cai Pinyan Lu Mingji Xia
+ PDF Chat	Dichotomy for Holant Problems with a Function on Domain Size 3	2013	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Dichotomy for holant* problems with a function on domain size 3	2013	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Holographic reduction for some counting problems	2011	Chen Yuan Haibin Kan
+	Holant problems and counting CSP	2009	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Complexity dichotomies of counting problems	2012	Lizhen Ji Yat Sun Poon Lo Yang Shing‐Tung Yau
+	The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems	2014	Jin‐Yi Cai Heng Guo Tyson Williams
+	The complexity of counting problems	2001	Dominic Welsh Amy Gale
+	From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems	2010	Jin‐Yi Cai Sangxia Huang Pinyan Lu
+	Computational complexity of counting problems on 3-regular planar graphs	2007	Mingji Xia Peng Zhang Wenbo Zhao
+	Complexity Dichotomies for Counting Problems	2017	Jin‐Yi Cai Xi Chen
+	Counting Complexity	1997	Lance Fortnow
+ PDF Chat	From Holant to #CSP and Back: Dichotomy for Holant c Problems	2010	Jin‐Yi Cai Sangxia Huang Pinyan Lu
+	On complexity of counting	2005	Marek Piotrów
+	Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy	2023	Jin‐Yi Cai Austen Z. Fan
+	Dichotomy theorems for holant problems	2010	Jin‐Yi Cai Michael Kowalczyk
+ PDF Chat	Holographic algorithms beyond matchgates	2018	Jin‐Yi Cai Heng Guo Tyson Williams
+ PDF Chat	Bipartite 3-regular counting problems with mixed signs	2023	Jin‐Yi Cai Austen Z. Fan Yin Liu

Works That Cite This (13)

Action	Title	Year	Authors
+	A computational proof of complexity of some restricted counting problems	2010	Jin‐Yi Cai Pinyan Lu Mingji Xia
+ PDF Chat	Block interpolation: A framework for tight exponential-time counting complexity	2018	Radu Curticapean
+ PDF Chat	Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP	2010	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	A Dichotomy for Real Weighted Holant Problems	2012	Sangxia Huang Pinyan Lu
+ PDF Chat	Gadgets and anti-gadgets leading to a complexity dichotomy	2012	Jin‐Yi Cai Michael Kowalczyk Tyson Williams
+	Dichotomy theorems for holant problems	2010	Jin‐Yi Cai Michael Kowalczyk
+	Holant Problems for Regular Graphs with Complex Edge Functions	2010	Michael Kowalczyk Jin‐Yi Cai
+	Complexity Dichotomies of Counting Problems.	2011	Pinyan Lu
+ PDF Chat	Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity	2015	Radu Curticapean
+	Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems	2010	Mingji Xia

Works Cited by This (12)

Action	Title	Year	Authors
+	A Complexity Dichotomy for Partition Functions with Mixed Signs	2009	Leslie Ann Goldberg Martin Grohe Mark Jerrum Marc Thurley
+ PDF Chat	Graph Homomorphisms with Complex Values: A Dichotomy Theorem	2010	Jin‐Yi Cai Xi Chen Pinyan Lu
+	Computational complexity of real functions	1982	Ker‐I Ko Harvey M. Friedman
+	The Complexity of Counting in Sparse, Regular, and Planar Graphs	2001	Salil Vadhan
+	Holant problems and counting CSP	2009	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil
+	The complexity of partition functions	2005	Andreĭ A. Bulatov Martin Grohe
+	Towards a dichotomy theorem for the counting constraint satisfaction problem	2006	Andreĭ A. Bulatov Víctor Dalmau
+	On counting homomorphisms to directed acyclic graphs	2007	Martin Dyer Leslie Ann Goldberg Mike Paterson