215 citations
- Microsoft (United States)US10 papers
- University of CambridgeGB5 papers
- Johns Hopkins UniversityUS4 papers
- Massachusetts Institute of TechnologyUS4 papers
- Tel Aviv UniversityIL4 papers
- University of California, BerkeleyUS4 papers
- Microsoft Research New England (United States)US3 papers
- University of British ColumbiaCA3 papers
- University of ChicagoUS3 papers
- University of MichiganUS3 papers
- University of WashingtonUS3 papers
- Argonne National LaboratoryUS2 papers
4 papers · 1 filter
Property Testing via Set-Theoretic Operations
Victor Chen, Madhu Sudan, Ning Xie
Given two testable properties and , under what conditions are the union, intersection or set-difference of these two properties also testable? We…
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Parikshit Gopalan, Adam Klivans, Raghu Meka
We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with…
Lower Bounds on Near Neighbor Search via Metric Expansion
Rina Panigrahy, Kunal Talwar, Udi Wieder
In this paper we show how the complexity of performing nearest neighbor (NNS) search on a metric space is related to the expansion of the metric space. Given a metric space we look…
On Revenue Maximization in Second-Price Ad Auctions
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin +1
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auct…