22 citations · 115 across the 31 of their papers we have counts for
4 papers · 1 filter
Polynomial-time trace reconstruction in the low deletion rate regime
Xi Chen, Anindya De, Chin Ho Lee +2
In the \emph{trace reconstruction problem}, an unknown source string is transmitted through a probabilistic \emph{deletion channel} which independently deletes ea…
Polynomial-time trace reconstruction in the smoothed complexity model
Xi Chen, Anindya De, Chin Ho Lee +2
In the \emph{trace reconstruction problem}, an unknown source string is sent through a probabilistic \emph{deletion channel} which independently deletes each bit…
Hedging in games: Faster convergence of external and swap regrets
Xi Chen, Binghui Peng
We consider the setting where players run the Hedge algorithm or its optimistic variant to play an -action game repeatedly for rounds. 1) For two-player games, we show that…
Learning and Testing Junta Distributions with Subcube Conditioning
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study the problems of learning and testing junta distributions on with respect to the uniform distribution, where a distribution is a -junta if its probabili…