60 citations · 237 across the 39 of their papers we have counts for
3 papers · 1 filter
Testing Symmetric Markov Chains from a Single Trajectory
Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin
Classical distribution testing assumes access to i.i.d. samples from the distribution that is being tested. We initiate the study of Markov chain testing, assuming access to a sing…
Tight Lower Bounds for Multiplicative Weights Algorithmic Families
Nick Gravin, Yuval Peres, Balasubramanian Sivan
We study the fundamental problem of prediction with expert advice and develop regret lower bounds for a large family of algorithms for this problem. We develop simple adversarial p…
Towards Optimal Algorithms for Prediction with Expert Advice
Nick Gravin, Yuval Peres, Balasubramanian Sivan
We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of…