From the 2 of 9 linked papers with an AI index.
4 papers · 1 filter
Testing Monotonicity of Real-Valued Functions on DAGs
Yuichi Yoshida
The paper investigates how to test whether real-valued functions on directed acyclic graphs are monotone, providing tight non‑adaptive query complexity bounds that depend on the si…
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 f…
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…
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…