The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Show other versions (2)

One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-call...

Deskribapen osoa

Xehetasun bibliografikoak
Egile Nagusiak:	Goldberg, L, Galanis, A
Formatua:	Journal article
Argitaratua:	Elsevier 2016

Antzeko izenburuak

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
nork: Goldberg, L, et al.
Argitaratua: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
nork: Galanis, A, et al.
Argitaratua: (2015)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
nork: Galanis, A, et al.
Argitaratua: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
nork: Galanis, A, et al.
Argitaratua: (2020)

The complexity of approximating the complex-valued Ising model on bounded degree graphs
nork: Galanis, A, et al.
Argitaratua: (2022)

Inapproximability of counting hypergraph colourings
nork: Galanis, A, et al.
Argitaratua: (2022)

On the distance energy of k-uniform hypergraphs
nork: Sharma Kshitij, et al.
Argitaratua: (2023-07-01)

A complexity trichotomy for approximately counting list H-colourings
nork: Goldberg, L, et al.
Argitaratua: (2016)

A complexity trichotomy for approximately counting list H-colourings
nork: Galanis, A, et al.
Argitaratua: (2017)

Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
nork: Alexandre Bazin, et al.
Argitaratua: (2023-04-01)

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
nork: Goldberg, L, et al.
Argitaratua: (2015)

Self-complementing permutations of k-uniform hypergraphs
nork: Artur Szymański, et al.
Argitaratua: (2009-01-01)

Super edge-magic labeling for 𝒌-uniform, complete 𝒌-uniform and complete 𝒌-uniform 𝒌-partite hypergraphs
nork: Ratinan Boonklurb, et al.
Argitaratua: (2021-04-01)

Constructing and sampling partite, 3-uniform hypergraphs with given degree sequence.
nork: András Hubai, et al.
Argitaratua: (2024-01-01)

Constructing and sampling partite, 3-uniform hypergraphs with given degree sequence
nork: András Hubai, et al.
Argitaratua: (2024-01-01)

Approximately counting H-colourings is #BIS-hard
nork: Galanis, A, et al.
Argitaratua: (2016)

Approximately counting H-colourings is BIS-Hard
nork: Galanis, A, et al.
Argitaratua: (2015)

A generalization of Hall's theorem for $k$-uniform $k$-partite hypergraphs
nork: Reza Jafarpour-Golzari
Argitaratua: (2019-09-01)

Sharp Bounds on the Spectral Radii of Uniform Hypergraphs concerning Diameter or Clique Number
nork: Qiannan Niu, et al.
Argitaratua: (2021-01-01)

On the Sizes of (k, l)-Edge-Maximal r-Uniform Hypergraphs
nork: Tian Yingzhi, et al.
Argitaratua: (2023-02-01)

On $\alpha$-spectral theory of a directed k-uniform hypergraph
nork: Gholam-Hasan Shirdel, et al.
Argitaratua: (2020-09-01)

The complexity of approximately counting retractions
nork: Focke, J, et al.
Argitaratua: (2020)

The complexity of approximately counting retractions
nork: Focke, J, et al.
Argitaratua: (2019)

Hypergraphs of bounded disjointness
nork: Scott, A, et al.
Argitaratua: (2014)

Bounds for the Energy of Hypergraphs
nork: Liya Jess Kurian, et al.
Argitaratua: (2024-11-01)

A sharp upper bound on the spectral radius of a nonnegative k-uniform tensor and its applications to (directed) hypergraphs
nork: Chuang Lv, et al.
Argitaratua: (2020-02-01)

A class of inequalities relating degrees of adjacent nodes to the average degree in edge-weighted uniform hypergraphs
nork: P. D. Johnson, et al.
Argitaratua: (2005-01-01)

Sombor index of uniform hypergraphs
nork: Xiuwen Wang, et al.
Argitaratua: (2024-10-01)

Bounds for the query complexity of approximate equilibria
nork: Goldberg, PW, et al.
Argitaratua: (2016)

Decomposing hypergraphs into k-colorable hypergraphs
nork: Gholamreza Omidi, et al.
Argitaratua: (2014-06-01)

The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
nork: Boix-Adserà, Enric, et al.
Argitaratua: (2022)

The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
nork: Boix-Adsera, Enric, et al.
Argitaratua: (2021)

On rainbow-free colourings of uniform hypergraphs
nork: Groot Koerkamp, R, et al.
Argitaratua: (2021)

On hamiltonian chain saturated uniform hypergraphs
nork: Aneta Dudek, et al.
Argitaratua: (2012-01-01)

On the α-Spectral Radius of Uniform Hypergraphs
nork: Guo Haiyan, et al.
Argitaratua: (2020-05-01)

A Note on Packing of Uniform Hypergraphs
nork: Konarski Jerzy, et al.
Argitaratua: (2022-11-01)

Almost Self-Complementary Uniform Hypergraphs
nork: Wojda Adam Paweł
Argitaratua: (2018-05-01)

On vertex independence number of uniform hypergraphs
nork: Chishti Tariq A., et al.
Argitaratua: (2014-06-01)

Decomposing complete 3-uniform hypergraph K_{n}^{(3)} into 7-cycles
nork: Meihua, et al.
Argitaratua: (2019-01-01)

Fast sampling via spectral independence beyond bounded-degree graphs
nork: Bezáková, I, et al.
Argitaratua: (2024)