报告时间：2026年4月1日 下午17:00开始
报 告 人：陈林(浙江大学)
报告地点：9-113
报告题目：Long Arithmetic Progressions in Dense and Sparse Subset Sums: A Computational Perspective
报告摘要：
Existence of long arithmetic progression in sumsets and subset sums has been studied extensively in the field of additive combinatorics. These additive combinatorics results play a central role in the recent progress of fundamental problems in theoretical computer science including Knapsack and Subset Sum. The non-constructiveness of relevant additive combinatorics results affects their application in algorithms. In particular, additive combinatorics-based algorithms for Subset Sum, including an $\tilde{O}(n)$-time algorithm for dense subset sum [Bringmann and Wellnitz '21] and an $\tilde{O}(n + \sqrt{a_{\max}t})$-time algorithm [Chen, Lian, Mao, and Zhang '24], work only for the decision version of the problem, but not for the search version. To find a solution, one has to spend a lot more time.
We study arithmetic progressions from a computational perspective: instead of merely knowing the existence of arithmetic progressions, we aim to construct it explicitly and find out how its terms can be represented using integers from the corresponding set. We show the followings can be done in near-linear time for long arithmetic progressions in: $kA$, the $k$-fold sum of an integer set $A$; $\mathcal{S}(A)$, the set of all subset sums of $A$, where $A$ is a set of nonnegative integers and $|A|$ is relatively large comparing to $\max(A)$ (the largest element in $A$); and the sumset of different sets, i.e., $A_1+A_2+\cdots+A_k$.
As an application, we can obtain: (i) an $\tilde{O}(n)$-time algorithm for the search version of dense subset sum, (ii). an $\tilde{O}(n + \sqrt{a_{\max}t})$-time algorithm for the search version of subset sum. Another application of our result is Unbounded Subset Sum, where each input integer can be used an infinite number of times. A classic result on the Frobenius problem [Erd{\"o}s and Graham '72] implies that for all $t \geq 2a^2_{\max}/n$, the decision version can be solved trivially in linear time. It remains unknown whether the search version can be solved in the same time. Our result implies that for all $t \geq ca^2_{\max}/n$ for some constant $c$, a solution for Unbounded Subset Sum can be obtained in $O(n \log a_{\max})$ time.
Our result builds upon the recent breakthrough in Sunflower lemma. In particular, we exploit the concept of spreadness (which is crucial in proving a sharper bound for Sunflower lemma) to design an efficient algorithm for computing a sunflower.
报告人简介：陈林博士，现为浙江大学百人计划研究员。2013年毕业于浙江大学。获得2024年运筹学会青年科技奖，现主持中国自然科学基金海外优青项目和面上项目。主要研究方向为组合优化，研究课题包括子集和，背包，排序，以及分块结构整数规划等问题的近似算法和参数算法。在SODA, STOC, FOCS等理论计算机顶级会议，以及SIAM Journal on Computing, Mathematical Programming, Mathematics of Operations Research等权威期刊上发表数十篇文章。
