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
Showing 2010 · cs.DSShow all
3 papers · 2 filters
cs.DS2010★ 5 cited
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…
cs.DS2010★ 24 cited
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…
cs.DS2010★ 30 cited
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…