215 citations
- Microsoft (United States)US16 papers
- University of CambridgeGB7 papers
- Massachusetts Institute of TechnologyUS5 papers
- Tel Aviv UniversityIL5 papers
- Johns Hopkins UniversityUS4 papers
- Microsoft Research New England (United States)US4 papers
- University of California, BerkeleyUS4 papers
- University of ChicagoUS4 papers
- University of WashingtonUS4 papers
- Stanford UniversityUS3 papers
- Technion – Israel Institute of TechnologyIL3 papers
- University of British ColumbiaCA3 papers
7 papers · 1 filter
Ranking and Tradeoffs in Sponsored Search Auctions
Ben Roberts, Dinan Gunawardena, Ian A. Kash +1
In a sponsored search auction, decisions about how to rank ads impose tradeoffs between objectives such as revenue and welfare. In this paper, we examine how these tradeoffs should…
How to Approximate A Set Without Knowing Its Size In Advance
Rasmus Pagh, Gil Segev, Udi Wieder
The dynamic approximate membership problem asks to represent a set S of size n, whose elements are provided in an on-line fashion, supporting membership queries without false negat…
Sensitivity of mixing times
Jian Ding, Yuval Peres
In this note, we demonstrate an instance of bounded-degree graphs of size , for which the total variation mixing time for the random walk is decreased by a factor of $\log n/ \l…
Online Learning for Time Series Prediction
Oren Anava, Elad Hazan, Shie Mannor +1
In this paper we address the problem of predicting a time series using the ARMA (autoregressive moving average) model, under minimal assumptions on the noise terms. Using regret mi…
Probabilistic Frame Induction
Jackie Chi Kit Cheung, Hoifung Poon, Lucy Vanderwende
In natural-language discourse, related events tend to appear near each other to describe a larger scenario. Such structures can be formalized by the notion of a frame (a.k.a. templ…
Convergent sequences of sparse graphs: A large deviations approach
Christian Borgs, Jennifer Chayes, David Gamarnik
In this paper we introduce a new notion of convergence of sparse graphs which we call Large Deviations or LD-convergence and which is based on the theory of large deviations. The n…