#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #Sat to approximate. We study #BIS in the general framework of two-state spin systems on bipart...

Detaylı Bibliyografya
Asıl Yazarlar:	Goldberg, L, Galanis, A, Cai, J, Guo, H, Jerrum, M, Stefankovic, D, Vigoda, E
Materyal Türü:	Journal article
Baskı/Yayın Bilgisi:	Pleiades Publishing 2015

Benzer Materyaller

Fast sampling via spectral independence beyond bounded-degree graphs
Yazar:: Bezáková, I, ve diğerleri
Baskı/Yayın Bilgisi: (2024)

Fast sampling via spectral independence beyond bounded-degree graphs
Yazar:: Bezakova, I, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

Approximately counting H-colourings is BIS-Hard
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2015)

Approximately counting H-colourings is #BIS-hard
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2015)

Sampling in uniqueness from the potts and random-cluster models on random regular graphs
Yazar:: Blanca, A, ve diğerleri
Baskı/Yayın Bilgisi: (2018)

On the chromatic uniqueness of certain bipartite graphs
Yazar:: Peng, Y.H.
Baskı/Yayın Bilgisi: (1991)

Fast algorithms for general spin systems on bipartite expanders
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2021)

Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

The complexity of approximating the complex-valued Ising model on bounded degree graphs
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
Yazar:: Goldberg, L, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
Yazar:: Goldberg, L, ve diğerleri
Baskı/Yayın Bilgisi: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2015)

GRAPH BIPARTITIONING AND THE BETHE SPIN-GLASS
Yazar:: Sherrington, D, ve diğerleri
Baskı/Yayın Bilgisi: (1987)

Counting shellings of complete bipartite graphs and trees
Yazar:: Gao, Yibo, ve diğerleri
Baskı/Yayın Bilgisi: (2021)

Pure pairs. IV. Trees in bipartite graphs
Yazar:: Scott, AD, ve diğerleri
Baskı/Yayın Bilgisi: (2023)

Metastability of the Potts ferromagnet on random regular graphs
Yazar:: Coja-Oghlan, A, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

Metastability of the Potts ferromagnet on random regular graphs
Yazar:: Coja-Oghlan, A, ve diğerleri
Baskı/Yayın Bilgisi: (2023)

Improved strong spatial mixing for colorings on trees
Yazar:: Efthymiou, C, ve diğerleri
Baskı/Yayın Bilgisi: (2019)

Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs.
Yazar:: McDiarmid, C, ve diğerleri
Baskı/Yayın Bilgisi: (2001)

Sampling in iniqueness from the Potts and random-cluster models on random regular graphs
Yazar:: Blanca, A, ve diğerleri
Baskı/Yayın Bilgisi: (2020)

Uniqueness for the 3-State antiferromagnetic Potts model on the tree
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2018)

Chromatically unique bipartite graphs with certain 3-independent partition numbers III
Yazar:: Hasni @ Abdullah, Roslan, ve diğerleri
Baskı/Yayın Bilgisi: (2007)

Application of bipartite graphs
Yazar:: Deng, Xiaohui
Baskı/Yayın Bilgisi: (2009)

Concatenating bipartite graphs
Yazar:: Chudnovsky, M, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

Irregular total labeling on complete bipartite graph and union complete bipartite graphs
Yazar:: Daoud, Jamal Ibrahim, ve diğerleri
Baskı/Yayın Bilgisi: (2010)

Fast mixing via polymers for random graphs with unbounded degree
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2021)

Fast mixing via polymers for random graphs with unbounded degree
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2022)

Chromaticity of Certain Bipartite Graphs
Yazar:: Hasni @ Abdullah, Roslan
Baskı/Yayın Bilgisi: (2005)

GRAPH BIPARTITIONING AND STATISTICAL-MECHANICS
Yazar:: Banavar, J, ve diğerleri
Baskı/Yayın Bilgisi: (1987)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2020)

Random walks on small world networks
Yazar:: Dyer, ME, ve diğerleri
Baskı/Yayın Bilgisi: (2020)

Swendsen-Wang algorithm on the mean-field Potts model
Yazar:: Galanis, A, ve diğerleri
Baskı/Yayın Bilgisi: (2018)

Algorithms for #BIS-hard problems on expander graphs
Yazar:: Jenssen, M, ve diğerleri
Baskı/Yayın Bilgisi: (2019)

Uniqueness of the entanglement measure for bipartite pure states and thermodynamics.
Yazar:: Vedral, V, ve diğerleri
Baskı/Yayın Bilgisi: (2002)

GRAPH BIPARTITIONING AND SPIN-GLASSES ON A RANDOM NETWORK OF FIXED FINITE VALENCE
Yazar:: Wong, K, ve diğerleri
Baskı/Yayın Bilgisi: (1987)

Hamilton cycles, minimum degree, and bipartite holes
Yazar:: McDiarmid, C, ve diğerleri
Baskı/Yayın Bilgisi: (2017)

Judicious partitions of bounded-degree graphs
Yazar:: Bollob�s, B, ve diğerleri
Baskı/Yayın Bilgisi: (2004)