7 papers · 1 filter
Stability Dichotomies for Boolean Constraint Satisfaction Problems
Chunyang Wang, Yuichi Yoshida
We study the stability of Boolean constraint satisfaction problems (CSPs) through the notion of average sensitivity (Varma and Yoshida, SODA 2021; SICOMP 2023). It measures the exp…
Sensitivity and Differential Privacy in Metric Voting with Distortion below Three
Shinsaku Sakaue, Kaito Fujii, Soh Kumabe +1
Voting rules aggregate individual preferences into collective decisions, but the rankings they receive contain only ordinal information. The metric distortion framework studies ord…
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…
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…
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…
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…