Fast sampling via spectral independence beyond bounded-degree graphs

Fast sampling via spectral independence beyond bounded-degree graphs

अन्य संस्करण दिखाएं (1)

Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniquene...

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों:	Bezakova, I, Galanis, A, Goldberg, L, Stefankovic, D
स्वरूप:	Conference item
भाषा:	English
प्रकाशित:	Leibniz International Proceedings in Informatics 2022

समान संसाधन

Fast sampling via spectral independence beyond bounded-degree graphs
द्वारा: Bezáková, I, और अन्य
प्रकाशित: (2024)

Inapproximability of the independent set polynomial in the complex plane
द्वारा: Bezakova, I, और अन्य
प्रकाशित: (2018)

Inapproximability of the independent set polynomial in the complex plane
द्वारा: Bezáková, I, और अन्य
प्रकाशित: (2020)

Fast mixing via polymers for random graphs with unbounded degree
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2022)

Fast mixing via polymers for random graphs with unbounded degree
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2021)

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
द्वारा: Goldberg, L, और अन्य
प्रकाशित: (2015)

Approximation via correlation decay when strong spatial mixing fails
द्वारा: Bezakova, I, और अन्य
प्रकाशित: (2019)

Approximation via correlation decay when strong spatial mixing fails
द्वारा: Bezakova, I, और अन्य
प्रकाशित: (2016)

The complexity of approximating the matching polynomial in the complex plane
द्वारा: Bezakova, I, और अन्य
प्रकाशित: (2021)

The complexity of approximating the complex-valued Ising model on bounded degree graphs
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2022)

Implementations and the independent set polynomial below the Shearer threshold
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2022)

Inapproximability of the independent set polynomial below the Shearer threshold
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2017)

Sampling in iniqueness from the Potts and random-cluster models on random regular graphs
द्वारा: Blanca, A, और अन्य
प्रकाशित: (2020)

Sampling in uniqueness from the potts and random-cluster models on random regular graphs
द्वारा: Blanca, A, और अन्य
प्रकाशित: (2018)

PTAS for maximum weight independent set problem with random weights in bounded degree graphs
द्वारा: Gamarnik, David, और अन्य
प्रकाशित: (2012)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
द्वारा: Goldberg, L, और अन्य
प्रकाशित: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
द्वारा: Goldberg, L, और अन्य
प्रकाशित: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2015)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2020)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2024)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
द्वारा: Galanis, A, और अन्य
प्रकाशित: (2023)

On the treewidths of graphs of bounded degree.
द्वारा: Yinglei Song, और अन्य
प्रकाशित: (2015-01-01)

Bounding Extremal Degrees of Edge-Independent Random Graphs Using Relative Entropy
द्वारा: Yilun Shang
प्रकाशित: (2016-02-01)

Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs.
द्वारा: Péter L Erdős, और अन्य
प्रकाशित: (2018-01-01)

Metastability of the Potts ferromagnet on random regular graphs
द्वारा: Coja-Oghlan, A, और अन्य
प्रकाशित: (2022)

Metastability of the Potts ferromagnet on random regular graphs
द्वारा: Coja-Oghlan, A, और अन्य
प्रकाशित: (2023)

Judicious partitions of bounded-degree graphs
द्वारा: Bollob�s, B, और अन्य
प्रकाशित: (2004)

Acyclic colourings of graphs with bounded degree
द्वारा: Mieczyslaw Borowiecki, और अन्य
प्रकाशित: (2010-01-01)

Cycle transversals in bounded degree graphs
द्वारा: Marina Groshaus, और अन्य
प्रकाशित: (2011-03-01)

New Bounds For Degree Sequence Of Graphs
द्वारा: Akbar Jahanbani
प्रकाशित: (2019-09-01)

Metric uniformization and spectral bounds for graphs
द्वारा: Kelner, Jonathan Adam, और अन्य
प्रकाशित: (2012)

Bounds for the Laplacian spectral radius of graphs
द्वारा: Kamal Lochan Patra, और अन्य
प्रकाशित: (2017-10-01)

Subdomination in Graphs with Upper-Bounded Vertex Degree
द्वारा: Darya Lemtyuzhnikova, और अन्य
प्रकाशित: (2023-06-01)

3-Paths in Graphs with Bounded Average Degree
द्वारा: Jendrol Stanislav, और अन्य
प्रकाशित: (2016-05-01)

Fast Spectral Clustering via Efficient Multilayer Anchor Graph
द्वारा: Yiwei Wei, और अन्य
प्रकाशित: (2024-01-01)

New bounds on domination and independence in graphs
द्वारा: Jochen Harant, और अन्य
प्रकाशित: (2023-01-01)

On Selkow’s Bound on the Independence Number of Graphs
द्वारा: Harant Jochen, और अन्य
प्रकाशित: (2019-08-01)

Acyclic improper colourings of graphs with bounded maximum degree
द्वारा: Addario-Berry, L, और अन्य
प्रकाशित: (2010)

A sharp upper bound on the independent 2-rainbow domination in graphs with minimum degree at least two
द्वारा: Rana Khoeilar, और अन्य
प्रकाशित: (2020-12-01)