2 papers
cs.DS2025
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Yuzhou Gu, Xin Li, Yinzhan Xu
In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability . In this paper, we obta…
math.PR2024
Entropy Contractions in Markov Chains: Half-Step, Full-Step and Continuous-Time
Pietro Caputo, Zongchen Chen, Yuzhou Gu +1
This paper considers the speed of convergence (mixing) of a finite Markov kernel with respect to the Kullback-Leibler divergence (entropy). Given a Markov kernel one defines ei…