Ce Jin is a fourth-year PhD student at MIT, co-advised by Virginia Vassilevska Williams and Ryan Williams. Previously, he was an undergraduate student in Yao Class, Tsinghua University. He is interested in theoretical computer science, in particular fine-grained complexity and algorithms.

He is visiting D1 group from MIT between July 13th and 26th.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

We revisit the classic #Knapsack problem, which asks to count the Boolean points $(x_1,x_2,\dots,x_n)\in \{0,1\}^n$ in a given half-space $\sum_{i=1}^n W_ix_i \le T$. This #P-complete problem is known to admit $(1 \pm \epsilon)$-approximation. Before this work, [Dyer, STOC 2003]'s $\tilde{O}(n^{2.5} + n^2 \epsilon^{-2})$-time randomized approximation scheme remains the fastest known in the natural regime of $\epsilon > 1/polylog(n)$.

In this paper, we give a randomized $(1 \pm \epsilon)$-approximation algorithm for #Knapsack in $\tilde{O}(n^{1.5}\epsilon^{-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:
- We decrease the sample complexity of Dyer's Monte Carlo method, by proving some structural lemmas for ``typical'' points in the half-space via hitting-set arguments, and appropriately setting the rounding scale.
- Instead of running a vanilla dynamic program on the rounded instance, we employ techniques from the growing field of pseudopolynomial-time Subset Sum algorithms, such as FFT, divide-and-conquer, and balls-into-bins hashing of [Bringmann, SODA 2017].

To implement these ideas, we also need other technical ingredients, including a surprising application of the recent Bounded Monotone (max,+)-Convolution algorithm by [Chi, Duan, Xie, and Zhang, STOC 2022] (adapted by [Bringmann, Dürr, and Polak, ESA 2024]), the notion of sum-approximation from [Gawrychowski, Markin, and Weimann, ICALP 2018]'s #Knapsack approximation scheme, and a two-phase extension of Dyer's framework for handling tiny weights.

Based on joint work with Weiming Feng (ETH Zürich).

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only