#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region

Jin‐Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, Eric Vigoda

Type: Article

Publication Date: 2014-01-01

Citations: 5

DOI: https://doi.org/10.4230/lipics.approx-random.2014.582

View Publication

Locations

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - View

Similar Works

Action	Title	Year	Authors
+	#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region	2015	Jin‐Yi Cai Andreas Galanis Leslie Ann Goldberg Heng Guo Mark Jerrum Daniel Štefankovič Eric Vigoda
+	The computational hardness of counting in two-spin models on d-regular graphs	2012	Allan Sly Nike Sun
+ PDF Chat	The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs	2012	Allan Sly Nike Sun
+ PDF Chat	Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results	2016	Andreas Galanis Daniel Štefankovič Eric Vigoda Linji Yang
+	The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs	2016	Andreas Galanis Leslie Ann Goldberg
+	The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs	2016	Andreas Galanis Leslie Ann Goldberg
+ PDF Chat	Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models	2016	Andreas Galanis Daniel Štefankovič Eric Vigoda
+	Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region	2014	Andreas Galanis Daniel Štefankovič Eric Vigoda
+	#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region	2015	LA Goldberg Andreas Galanis J-Y Cai Hongye Guo Mark Jerrum Daniel Štefankovič Eric Vigoda
+	Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results	2013	Andreas Galanis Daniel Štefankovič Eric Vigoda Linji Yang
+	The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs	2015	Andreas Galanis Leslie Ann Goldberg
+	Approximately counting independent sets of a given size in bounded-degree graphs	2021	Ewan Davies Will Perkins
+	Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems	2016	Heng Guo Pinyan Lu
+	Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results	2014	Andreas Galanis Daniel Štefankovič Eric Vigoda Linji Yang
+	The complexity of approximately counting in 2-spin systems on <i>k</i>-uniform bounded-degree hypergraphs	2015	Andreas Galanis Leslie Ann Goldberg
+	Algorithms for #BIS-hard problems on expander graphs	2018	Matthew Jenssen Peter Keevash Will Perkins
+ PDF Chat	Inapproximability after Uniqueness Phase Transition in Two-Spin Systems	2012	Jin‐Yi Cai Xi Chen Heng Guo Pinyan Lu
+	Inapproximability After Uniqueness Phase Transition in Two-Spin Systems	2012	Jin‐Yi Cai Xi Chen Heng Guo Pinyan Lu
+	Computational Transition at the Uniqueness Threshold	2010	Allan Sly
+ PDF Chat	Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	2023	Ewan Davies Will Perkins

Works That Cite This (5)

Action	Title	Year	Authors
+	The Complexity of Ferromagnetic Two-spin Systems with External Fields	2014	Jing‐Cheng Liu Pinyan Lu Chihao Zhang
+ PDF Chat	Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models	2016	Andreas Galanis Daniel Štefankovič Eric Vigoda
+	#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region	2015	Jin‐Yi Cai Andreas Galanis Leslie Ann Goldberg Heng Guo Mark Jerrum Daniel Štefankovič Eric Vigoda
+	Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems	2015	Heng Guo Pinyan Lu
+	Counting hypergraph matchings up to uniqueness threshold	2015	Renjie Song Yitong Yin Jinman Zhao

Works Cited by This (0)

Action	Title	Year	Authors