7k citations
- University of California, Santa BarbaraUS109 papers
- Microsoft Research (United Kingdom)GB50 papers
- ETH ZurichCH46 papers
- University of California, BerkeleyUS45 papers
- University of Maryland, College ParkUS43 papers
- Carnegie Mellon UniversityUS41 papers
- Stanford UniversityUS39 papers
- University of WashingtonUS37 papers
- Cornell UniversityUS32 papers
- Princeton UniversityUS32 papers
- California Institute of TechnologyUS28 papers
- Microsoft Research New York City (United States)25 papers
Showing 2012 · cs.DSShow all
2 papers · 2 filters
cs.DS2012★ 1 cited
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
Konstantin Makarychev
We prove that the Bounded Occurrence Ordering k-CSP Problem is not approximation resistant. We give a very simple local search algorithm that always performs better than the random…
cs.DS2012★ 14 cited
On Privacy-Preserving Histograms
Shuchi Chawla, Cynthia Dwork, Frank McSherry +1
We advance the approach initiated by Chawla et al. for sanitizing (census) data so as to preserve the privacy of respondents while simultaneously extracting "useful" statistical in…