Approximation via correlation decay when strong spatial mixing fails

Approximation via correlation decay when strong spatial mixing fails

Taispeáin leaganacha eile (1)

Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of antiferromagnetic 2-spin models. Previous analyses of correlation-decay algorithms implicitly...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Bezakova, I, Galanis, A, Goldberg, L, Guo, H, Stefankovic, D
Formáid:	Journal article
Foilsithe / Cruthaithe:	Society for Industrial and Applied Mathematics 2019

Míreanna comhchosúla

Approximation via correlation decay when strong spatial mixing fails
de réir: Bezakova, I, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximating the matching polynomial in the complex plane
de réir: Bezakova, I, et al.
Foilsithe / Cruthaithe: (2021)

Fast sampling via spectral independence beyond bounded-degree graphs
de réir: Bezáková, I, et al.
Foilsithe / Cruthaithe: (2024)

Fast sampling via spectral independence beyond bounded-degree graphs
de réir: Bezakova, I, et al.
Foilsithe / Cruthaithe: (2022)

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

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)

Implementations and the independent set polynomial below the Shearer threshold
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

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

When omnigeneity fails
de réir: Parra, F, et al.
Foilsithe / Cruthaithe: (2014)

Fast mixing via polymers for random graphs with unbounded degree
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2021)

Fast mixing via polymers for random graphs with unbounded degree
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

Finding Bc(3S) states via their strong decays
de réir: Rui Ding, et al.
Foilsithe / Cruthaithe: (2021-05-01)

Approximately counting H-colourings is BIS-Hard
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2015)

Approximately counting H-colourings is #BIS-hard
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2015)

When normality fails
de réir: Richard Mohr
Foilsithe / Cruthaithe: (2022-06-01)

When logic fails
de réir: Justin Phan, MBBS, FRACP, et al.
Foilsithe / Cruthaithe: (2023-10-01)

The complexity of approximating the complex-valued Potts model
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

A complexity trichotomy for approximately counting list H-colourings
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2017)

A complexity trichotomy for approximately counting list H-colourings
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2020)

When flow diverters fail
de réir: Marco Zenteno, et al.
Foilsithe / Cruthaithe: (2016-12-01)

When Mendelian randomisation fails
de réir: Martin Kohlmeier, et al.

Strong reciprocal dependencies as exceptions when correlations are weak
de réir: M. M. Basimov
Foilsithe / Cruthaithe: (2024-06-01)

Approximating pairwise correlations in the Ising model
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2019)

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2015)

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

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

The complexity of approximating the complex-valued Ising model on bounded degree graphs
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

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)

#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)

Strong spatial mixing for list coloring of graphs
de réir: Gamarnik, David, et al.
Foilsithe / Cruthaithe: (2015)

Correlation Decay in Random Decision Networks
de réir: Gamarnik, David, et al.
Foilsithe / Cruthaithe: (2019)

The Ape Lottery: Chimpanzees Fail To Consider Spatial Information When Drawing Statistical Inferences
de réir: Johanna Eckert, et al.
Foilsithe / Cruthaithe: (2021-08-01)

When We Fail to Understand Ourselves
de réir: Ragnar M. Bergem
Foilsithe / Cruthaithe: (2022-11-01)