From the 2 of 8 linked papers with an AI index.
8 papers
Sensitivity and Differential Privacy in Metric Voting with Distortion below Three
Shinsaku Sakaue, Kaito Fujii, Soh Kumabe +1
The paper proposes randomized voting rules that achieve a metric distortion slightly below three while maintaining low worst‑case sensitivity and providing approximate differential…
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…
From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
Shinsaku Sakaue, Yuichi Yoshida
We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. By extending the batch-to…
Noise Stability of Transformer Models
Themistoklis Haris, Zihan Zhang, Yuichi Yoshida
Understanding simplicity biases in deep learning offers a promising path toward developing reliable AI. A common metric for this, inspired by Boolean function analysis, is average…