1.5k citations
- Massachusetts Institute of TechnologyUS194 papers
- Centre National de la Recherche ScientifiqueFR33 papers
- Harvard UniversityUS29 papers
- University of California, BerkeleyUS24 papers
- California Institute of TechnologyUS22 papers
- Northeastern UniversityUS22 papers
- University of CambridgeGB18 papers
- Cornell UniversityUS17 papers
- Kavli Institute for Particle Astrophysics and CosmologyUS17 papers
- Princeton UniversityUS17 papers
- MIT Computer Science and Artificial Intelligence LaboratoryUS16 papers
- Sorbonne UniversitéFR16 papers
Showing 2011 · cs.DSShow all
3 papers · 2 filters
cs.DS2011★ 2 cited
Space-efficient Local Computation Algorithms
Noga Alon, Ronitt Rubinfeld, Shai Vardi +1
Recently Rubinfeld et al. (ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called \emph{local computation algorithms}. In this model, a computation problem …
cs.DS2011
Faster Information Dissemination in Dynamic Networks via Network Coding
Bernhard Haeupler, David Karger
We use network coding to improve the speed of distributed computation in the dynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model an adversary adaptively choos…
cs.DS2011
High-Confidence Predictions under Adversarial Uncertainty
Andrew Drucker
We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to…