73 citations · 347 across the 51 of their papers we have counts for
Showing 2010 · cs.DSShow all
2 papers · 2 filters
cs.DS2010★ 8 cited
Almost Optimal Explicit Johnson-Lindenstrauss Transformations
Raghu Meka
The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known c…
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…