Copertina

Near-Optimal Parallel Approximate Counting via Sampling

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Harris, David G., Kolmogorov, Vladimir, Liu, Hongyang, Yin, Yitong, Zhang, Yiyao
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Work-Efficient Parallel Counting via Sampling
di: Liu, Hongyang, et al.
Pubblicazione: (2024)

Simple parallel estimation of the partition ratio for Gibbs distributions
di: Harris, David G., et al.
Pubblicazione: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
di: Harris, David G., et al.
Pubblicazione: (2020)

Parameter estimation for Gibbs distributions
di: Harris, David G., et al.
Pubblicazione: (2020)

A Sampling Lovász Local Lemma for Large Domain Sizes
di: Wang, Chunyang, et al.
Pubblicazione: (2023)

Subquadratic Counting via Perfect Marginal Sampling
di: Chen, Xiaoyu, et al.
Pubblicazione: (2026)

Parallelize Single-Site Dynamics up to Dobrushin Criterion
di: Liu, Hongyang, et al.
Pubblicazione: (2021)

Parallel Sampling via Counting
di: Anari, Nima, et al.
Pubblicazione: (2024)

Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
di: Chen, Xiaoyu, et al.
Pubblicazione: (2026)

Efficient Parallel Ising Samplers via Localization Schemes
di: Chen, Xiaoyu, et al.
Pubblicazione: (2025)

Spectral Independence Beyond Total Influence on Trees and Related Graphs
di: Chen, Xiaoyu, et al.
Pubblicazione: (2024)

Rapid Mixing at the Uniqueness Threshold
di: Chen, Xiaoyu, et al.
Pubblicazione: (2024)

Rapid Mixing on Random Regular Graphs beyond Uniqueness
di: Chen, Xiaoyu, et al.
Pubblicazione: (2025)

Approximating the total variation distance between spin systems
di: Feng, Weiming, et al.
Pubblicazione: (2025)

Tight Bounds for Sampling q-Colorings via Coupling from the Past
di: Ding, Tianxing, et al.
Pubblicazione: (2025)

Phase Transitions via Complex Extensions of Markov Chains
di: Liu, Jingcheng, et al.
Pubblicazione: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
di: Kolmogorov, Vladimir, et al.
Pubblicazione: (2026)

A computational study of Gomory-Hu construction tree algorithms
di: Kolmogorov, Vladimir
Pubblicazione: (2022)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
di: Kolmogorov, Vladimir
Pubblicazione: (2023)

OrderedCuts: A new approach for computing Gomory-Hu tree
di: Kolmogorov, Vladimir
Pubblicazione: (2022)

Markov Chains Approximate Message Passing
di: Rajaraman, Amit, et al.
Pubblicazione: (2025)

Approximate Counting in Local Lemma Regimes
di: Mann, Ryan L., et al.
Pubblicazione: (2025)

Local Gibbs sampling beyond local uniformity
di: Liu, Hongyang, et al.
Pubblicazione: (2025)

Sampling Sphere Packings with Continuum Glauber Dynamics
di: Kuchukova, Aiya, et al.
Pubblicazione: (2026)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
di: Wang, Yulin, et al.
Pubblicazione: (2023)

Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
di: He, Yuchen, et al.
Pubblicazione: (2026)

Faster Mixing of the Jerrum-Sinclair Chain
di: Chen, Xiaoyu, et al.
Pubblicazione: (2025)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
di: Arkhipov, Pavel, et al.
Pubblicazione: (2026)

Faster algorithms for packing forests in graphs and related problems
di: Arkhipov, Pavel, et al.
Pubblicazione: (2024)

Greedy matroid base packings with applications to dynamic graph density and orientations
di: Arkhipov, Pavel, et al.
Pubblicazione: (2025)

On Sampling from Ising Models with Spectral Constraints
di: Galanis, Andreas, et al.
Pubblicazione: (2024)

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
di: Lev-Ran, Asaf, et al.
Pubblicazione: (2026)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
di: Carlson, Charlie, et al.
Pubblicazione: (2024)

Parallel Sampling via Autospeculation
di: Anari, Nima, et al.
Pubblicazione: (2025)

Scalable Algorithms for Approximate DNF Model Counting
di: Burkhardt, Paul, et al.
Pubblicazione: (2026)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
di: Moka, Sarat, et al.
Pubblicazione: (2026)

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
di: Liu, Kuikui, et al.
Pubblicazione: (2024)

Semirandom Planted Clique via 1-norm Isometry Property
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2025)

Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
di: Chen, Xiaoyu, et al.
Pubblicazione: (2024)

Hardness of sampling solutions from the Symmetric Binary Perceptron
di: Alaoui, Ahmed El, et al.
Pubblicazione: (2024)