Cover Image

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Moka, Sarat, Vahedi, Ava
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

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

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
by: Das, Avinandan
Published: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
by: Jain, Vishesh, et al.
Published: (2026)

Scheduling Problems with Constrained Rejections
by: Davies, Sami, et al.
Published: (2025)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
by: Kocurek, Nicholas, et al.
Published: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

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

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

On the Advantage of Adaptivity for Sampling with Cell Probes
by: Byramji, Farzan, et al.
Published: (2026)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
by: Fu, Daniel, et al.
Published: (2026)

A computational phase transition for learning-to-sample from Ising models
by: Risteski, Andrej, et al.
Published: (2026)

Stable algorithms cannot reliably find isolated perceptron solutions
by: Gong, Shuyang, et al.
Published: (2026)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
by: Kızıldağ, Eren C.
Published: (2023)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
by: R., Abhishek Hegade K., et al.
Published: (2025)

Discrepancy Algorithms for the Binary Perceptron
by: Li, Shuangping, et al.
Published: (2024)

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

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Strong Low Degree Hardness for the Number Partitioning Problem
by: Mallarapu, Rushil, et al.
Published: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Improved Stabilizer Estimation via Bell Difference Sampling
by: Grewal, Sabee, et al.
Published: (2023)

Efficient Rejection Sampling in the Entropy-Optimal Range
by: Draper, Thomas L., et al.
Published: (2025)