Approximately Counting Knapsack Solutions in Subquadratic Time

We revisit the classic #Knapsack problem, which asks to count the Boolean points (x 1 , x 2 , . . . , x n ) ∈ 0, 1 n in a given half-space n i=1 W i x i ≤ T . This #P-complete problem is known to admit (1±ε)-approximation. Before this work, [Dyer, STOC 2003]'s O(n 2.5 +n 2 ε -2 )-time randomized approximation scheme remains the fastest known in the natural regime of ε ≥ 1/ poly log n.

In this paper, we give a randomized (1 ± ε)-approximation algorithm for #Knapsack in O(n 1.5 ε -2 ) time (in the standard word-RAM model), achieving the first sub-quadratic dependence on n. Such sub-quadratic running time is rare in the approximate counting literature in general, as a large class of algorithms naturally faces a quadratic-time barrier.

Our algorithm follows Dyer's framework, which reduces #Knapsack to the task of sampling (and approximately counting) solutions in a randomly rounded instance with poly(n)-bounded integer weights. We refine Dyer's framework using the following ideas: * This work was done in part while two authors were visiting the Simons Institute for the Theory of Computing.