24 citations · 87 across the 36 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2019
Finding Skewed Subcubes Under a Distribution
Parikshit Gopalan, Roie Levin, Udi Wieder
Say that we are given samples from a distribution over an -dimensional space. We expect or desire to behave like a product distribution (or a -wise independent distri…
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…