24 citations · 39 across the 3 of their papers we have counts for
3 papers
cs.CC2012★ 4 cited
DNF Sparsification and a Faster Deterministic Counting Algorithm
Parikshit Gopala, Raghu Meka, Omer Reingold
Given a DNF formula on n variables, the two natural size measures are the number of terms or size s(f), and the maximum width of a term w(f). It is folklore that short DNF formulas…
cs.DS2012★ 11 cited
Constructive Discrepancy Minimization by Walking on The Edges
Shachar Lovett, Raghu Meka
Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spenc…
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…