3 citations · 3 across the 5 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Approximate Colorwise Tensorization of Entropy and Optimal Mixing of the Wang-Swendsen-Kotecký Dynamics
Chunyang Wang, Yuichi Yoshida, Zihan Zhang
We study the mixing time of Wang-Swendsen-Kotecký (WSK) dynamics for uniformly sampling proper -colorings. The WSK dynamics is widely used in statistical physics for sampling fr…
cs.DS2026
Sensitivity Lower Bounds via Locally Testable Codes
Yuichi Yoshida, Zihan Zhang
Sensitivity quantifies how far an algorithm's output can move in Hamming distance when a single input element is perturbed. We present a general scheme turning any locally testable…
cs.DS2025
Low-Sensitivity Matching via Sampling from Gibbs Distributions
Yuichi Yoshida, Zihan Zhang
In this work, we study the maximum matching problem from the perspective of sensitivity. The sensitivity of an algorithm on a graph is defined as the maximum Wasserstein di…