Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region

<p style="text-align:justify;"> A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree Δ undergoes a...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Galanis, A, Stefankovic, D, Vigoda, E
Formáid:	Journal article
Foilsithe / Cruthaithe:	Association for Computing Machinery 2015

Míreanna comhchosúla

Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2016)

Inapproximability of the independent set polynomial below the Shearer threshold
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2017)

Inapproximability of the independent set polynomial in the complex plane
de réir: Bezáková, I, et al.
Foilsithe / Cruthaithe: (2020)

Inapproximability of the independent set polynomial in the complex plane
de réir: Bezakova, I, et al.
Foilsithe / Cruthaithe: (2018)

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2015)

Inapproximability of counting hypergraph colourings
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

Improved strong spatial mixing for colorings on trees
de réir: Efthymiou, C, et al.
Foilsithe / Cruthaithe: (2019)

Approximation algorithms and inapproximability of partition functions of spin systems
de réir: Yang, K
Foilsithe / Cruthaithe: (2019)

Swendsen-Wang algorithm on the mean-field Potts model
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2018)

Constant inapproximability for PPA
de réir: Deligkas, A, et al.
Foilsithe / Cruthaithe: (2025)

Constant inapproximability for PPA
de réir: Deligkas, A, et al.
Foilsithe / Cruthaithe: (2022)

Cautionary Tales of Inapproximability
de réir: Budden, David, et al.
Foilsithe / Cruthaithe: (2017)

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2016)

Constant inapproximability for Fisher markets
de réir: Deligkas, A, et al.
Foilsithe / Cruthaithe: (2024)

Pure-Circuit: tight inapproximability for PPAD
de réir: Deligkas, A, et al.
Foilsithe / Cruthaithe: (2024)

Pure-circuit: strong inapproximability for PPAD
de réir: Deligkas, A, et al.
Foilsithe / Cruthaithe: (2022)

Nonuniqueness of infinity ground states
de réir: Hynd, Ryan, et al.
Foilsithe / Cruthaithe: (2016)

The inapproximability for the $(0,1)$-additive number
de réir: Arash Ahadi, et al.
Foilsithe / Cruthaithe: (2016-06-01)

Uniqueness for the 3-State antiferromagnetic Potts model on the tree
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2018)

Nonuniqueness of Green’s functions at special points
de réir: Makoto Natsuume, et al.
Foilsithe / Cruthaithe: (2019-12-01)

Nonuniqueness and fractional index convolution complementarity problems
de réir: David E. Stewart
Foilsithe / Cruthaithe: (2014-10-01)

Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
de réir: Demaine, Erik D, et al.
Foilsithe / Cruthaithe: (2019)

Tight inapproximability of Nash equilibria in public goods games
de réir: Do Dinh, J, et al.
Foilsithe / Cruthaithe: (2024)

Sampling in uniqueness from the potts and random-cluster models on random regular graphs
de réir: Blanca, A, et al.
Foilsithe / Cruthaithe: (2018)

Sampling in iniqueness from the Potts and random-cluster models on random regular graphs
de réir: Blanca, A, et al.
Foilsithe / Cruthaithe: (2020)

Nonuniqueness in a minimal model for cell motility
de réir: Gallimore, L, et al.
Foilsithe / Cruthaithe: (2011)

Uniqueness and nonuniqueness criteria for ordinary differential equations /
de réir: 274976 Agarwal, R. P., et al.
Foilsithe / Cruthaithe: (1993)

ON NONUNIQUENESS FOR THE ANISOTROPIC CALDERÓN PROBLEM WITH PARTIAL DATA
de réir: THIERRY DAUDÉ, et al.
Foilsithe / Cruthaithe: (2020-01-01)

Inapproximability of Unique Games in Fixed-Point Logic with Counting
de réir: Jamie Tucker-Foltz
Foilsithe / Cruthaithe: (2024-04-01)

Approximation and inapproximability results on balanced connected partitions of graphs
de réir: Frédéric Chataigner, et al.
Foilsithe / Cruthaithe: (2007-01-01)

Approximation and Inapproximability Results on Balanced Connected Partitions of Graphs
de réir: Yoshiko Wakabayashi, et al.
Foilsithe / Cruthaithe: (2007-01-01)

Metastability of the Potts ferromagnet on random regular graphs
de réir: Coja-Oghlan, A, et al.
Foilsithe / Cruthaithe: (2022)

Metastability of the Potts ferromagnet on random regular graphs
de réir: Coja-Oghlan, A, et al.
Foilsithe / Cruthaithe: (2023)

Uniqueness and nonuniqueness of limits of Teichmüller harmonic map flow
de réir: Kohout, J, et al.
Foilsithe / Cruthaithe: (2020)

Uniqueness and nonuniqueness of limits of Teichmüller harmonic map flow
de réir: Kohout, J, et al.
Foilsithe / Cruthaithe: (2020)

Nonunique Coincidence Point Results via Admissible Mappings
de réir: Erdal Karapınar, et al.
Foilsithe / Cruthaithe: (2021-01-01)

Compatible and Incompatible Nonuniqueness Conditions for the Classical Cauchy Problem
de réir: Josef Diblík, et al.
Foilsithe / Cruthaithe: (2011-01-01)

Recent Advances on the Results for Nonunique Fixed in Various Spaces
de réir: Erdal Karapınar
Foilsithe / Cruthaithe: (2019-06-01)

ALTERNANT SPIN WAVES IN HEISENBERG ANTIFERROMAGNET
de réir: Abraham, D, et al.
Foilsithe / Cruthaithe: (1967)

Antiferromagnetic spin current rectifier
de réir: Roman Khymyn, et al.
Foilsithe / Cruthaithe: (2017-05-01)