Cover Image

Strong spatial mixing for colorings on trees and its algorithmic applications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Zongchen, Liu, Kuikui, Mani, Nitya, Moitra, Ankur
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Independence via Stability and Applications to Holant-Type Problems
by: Chen, Zongchen, et al.
Published: (2021)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
by: Kunisky, Dmitriy, et al.
Published: (2023)

Boltzmann Sampling for Powersets without an Oracle
by: Peyen, Jean
Published: (2026)

Integrating High-Dimensional Functions Deterministically
by: Gamarnik, David, et al.
Published: (2024)

The Compilability Thresholds of 2-CNF to OBDD
by: de Colnet, Alexis, et al.
Published: (2026)

Cycle-factors of regular graphs via entropy
by: Christoph, Micha, et al.
Published: (2025)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
by: Bansal, Nikhil, et al.
Published: (2025)

Probabilistic estimates of the diameters of the Rubik's Cube groups
by: Hirata, So
Published: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
by: Bernshteyn, Anton, et al.
Published: (2024)

Random local access for sampling k-SAT solutions
by: Dong, Dingding, et al.
Published: (2024)

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
by: Liu, Jingcheng, et al.
Published: (2026)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

The Strong Birthday Problem Revisited
by: Tripathy, Chijul B.
Published: (2025)

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

Improved bounds for coloring locally sparse hypergraphs
by: Iliopoulos, Fotis
Published: (2020)

The Squishy Grid Problem
by: Cai, Zixi, et al.
Published: (2025)

On zeros and algorithms for disordered systems: mean-field spin glasses
by: Bencs, Ferenc, et al.
Published: (2025)

Parameterised algorithms for temporally satisfying reconfiguration problems
by: Davot, Tom, et al.
Published: (2025)

Efficient algorithms for the Potts model on small-set expanders
by: Carlson, Charles, et al.
Published: (2020)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

A Method for Generating Connected Erdos-Renyi Random Graphs
by: Chinyaev, Boris
Published: (2025)

Sharp Online Hardness for Large Balanced Independent Sets
by: Dhawan, Abhishek, et al.
Published: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2026)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

On the complexity of finding a spanning even tree in a graph
by: Hanaka, Tesshu, et al.
Published: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

Sink-free orientations: a local sampler with applications
by: Anand, Konrad, et al.
Published: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
by: An, Shinwoo, et al.
Published: (2025)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Counterexamples to a Weitz-Style Reduction for Multispin Systems
by: Liu, Kuikui, et al.
Published: (2024)

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

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

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
by: Chen, Yu, et al.
Published: (2023)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
by: Chen, Yu, et al.
Published: (2024)

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

A Tight Bound on Localization of Electrical Flows
by: Gurel-Gurevich, Ori, et al.
Published: (2026)