4 papers · 1 filter
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…
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…
Testing Monotonicity of Real-Valued Functions on DAGs
Yuichi Yoshida
We study monotonicity testing of real-valued functions on directed acyclic graphs (DAGs) with vertices. Let and be the numbers of edges in the transitive reduction a…
Courcelle's Theorem for Lipschitz Continuity
Tatsuya Gima, Soh Kumabe, Yuichi Yoshida
Lipschitz continuity of algorithms, introduced by Kumabe and Yoshida (FOCS'23), measures the stability of an algorithm against small input perturbations. Algorithms with small Lips…