research
∙
12/31/2020
Consensus with Bounded Space and Minimal Communication
Population protocols are a fundamental model in distributed computing, w...
share
research
∙
08/03/2019
Multiplayer Bandit Learning, from Competition to Cooperation
The stochastic multi-armed bandit problem is a classic model illustratin...
research
∙
06/12/2019
Sorted Top-k in Rounds
We consider the sorted top-k problem whose goal is to recover the top-k ...
research
∙
04/28/2019
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
We consider the non-stochastic version of the (cooperative) multi-player...
research
∙
01/07/2019
Communication cost of consensus for nodes with limited memory
Motivated by applications in blockchains and sensor networks, we conside...
research
∙
08/14/2018
Testing Graph Clusterability: Algorithms and Lower Bounds
We consider the problem of testing graph cluster structure: given access...
research
∙
07/30/2018
Online Learning with an Almost Perfect Expert
We study the online learning problem where a forecaster makes a sequence...
research
∙
07/18/2018
Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
We prove new results on lazy random walks on finite graphs. To start, we...
research
∙
01/15/2018
Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
The deletion-insertion channel takes as input a bit string x∈{0,1}^n, a...
research
∙
11/10/2017
How fragile are information cascades?
It is well known that sequential decision making may lead to information...
research
∙
09/04/2017
Estimating graph parameters via random walks with restarts
In this paper we discuss the problem of estimating graph parameters from...
research
∙
08/24/2017
Mixing time estimation in reversible Markov chains from a single sample path
The spectral gap γ of a finite, ergodic, and reversible Markov chain is ...
research
∙
02/19/2015
Approval Voting and Incentives in Crowdsourcing
The growing need for labeled training data has made crowdsourcing an imp...
research
∙
12/12/2012