Imagen de Portada

Perfect sampling from rapidly mixing Markov chains

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Göbel, Andreas, Liu, Jingcheng, Manurangsi, Pasin, Pappik, Marcus
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Probability
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Perfect Sampling for Hard Spheres from Strong Spatial Mixing
por: Anand, Konrad, et al.
Publicado: (2023)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
por: Kamath, Pritish, et al.
Publicado: (2026)

Uniqueness of locally stable Gibbs point processes via spatial birth-death dynamics
por: Baguley, Samuel, et al.
Publicado: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
por: S., Karthik C., et al.
Publicado: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
por: Laekhanukit, Bundit, et al.
Publicado: (2026)

Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
por: Göbel, Andreas, et al.
Publicado: (2025)

Asymptotic Fair Division: Chores Are Easier Than Goods
por: Manurangsi, Pasin, et al.
Publicado: (2025)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
por: Epasto, Alessandro, et al.
Publicado: (2026)

Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions
por: Baguley, Samuel, et al.
Publicado: (2025)

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations
por: Göbel, Andreas, et al.
Publicado: (2026)

From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models
por: Friedrich, Tobias, et al.
Publicado: (2024)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
por: Li, Zihan, et al.
Publicado: (2024)

Critical window for approximate counting in dense Ising models
por: Galanis, Andreas, et al.
Publicado: (2026)

A simple proof of local universality for roots of Kac polynomials
por: Michelen, Marcus, et al.
Publicado: (2025)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
por: Tulsiani, Madhur, et al.
Publicado: (2024)

The Probability Spaces of QuickSort
por: Nadareishvili, George, et al.
Publicado: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
por: Williamson, Christopher
Publicado: (2026)

Lines in Every Direction with No ee-Random Points
por: Lutz, Neil, et al.
Publicado: (2025)

Rigorous Implications of the Low-Degree Heuristic
por: Hsieh, Jun-Ting, et al.
Publicado: (2026)

Inconsistency Probability of Sparse Equations over F2
por: Horak, P., et al.
Publicado: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Perfect t-embeddings of doubly periodic Aztec diamonds
por: Berggren, Tomas, et al.
Publicado: (2025)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
por: Kush, Deepanshu
Publicado: (2026)

On hardness of computing analytic Brouwer degree
por: Chakraborty, Somnath
Publicado: (2023)

Permanents of random matrices over finite fields
por: Hunter, Zach, et al.
Publicado: (2026)

Optimal Union Probability Interval Is NP-Hard
por: Kaski, Petteri, et al.
Publicado: (2026)

Polymer Dynamics via Cliques: New Conditions for Approximations
por: Friedrich, Tobias, et al.
Publicado: (2020)

Pseudorandom Permutations from Random Reversible Circuits
por: He, William, et al.
Publicado: (2024)

Asymptotic Analysis of Weighted Fair Division
por: Manurangsi, Pasin, et al.
Publicado: (2025)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
por: Gamarnik, David, et al.
Publicado: (2023)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
por: Huang, Neng, et al.
Publicado: (2024)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
por: Amireddy, Prashanth, et al.
Publicado: (2025)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
por: Li, Cheuk Ting
Publicado: (2024)

Computational lower bounds for multi-frequency group synchronization
por: Kireeva, Anastasia, et al.
Publicado: (2024)

Matrix Chaos Inequalities and Chaos of Combinatorial Type
por: Bandeira, Afonso S., et al.
Publicado: (2024)

Communication with Imperfectly Shared Randomness
por: Canonne, Clément L., et al.
Publicado: (2014)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
por: Guruswami, Venkatesan, et al.
Publicado: (2021)

Separating complexity classes of LCL problems on grids
por: Berlow, Katalin, et al.
Publicado: (2025)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
por: Aivasiliotis, Panagiotis, et al.
Publicado: (2025)

Polynomial-time sampling despite disorder chaos
por: Ma, Eric, et al.
Publicado: (2025)