论文标题
关于平均案例k-sum的硬度
On the Hardness of Average-case k-SUM
论文作者
论文摘要
在这项工作中，我们展示了第一个最糟糕的案例减少经典$ k $ - $ sum问题。 $ k $ -sum实例是$ m $整数的集合，$ k $ sum问题的目标是找到$ k $元素的子集，总计为$ 0 $。在平均值版本中，$ m $元素是从某个间隔$ [-U，U] $中随机选择的。 我们考虑$ m $足够大的总设置（相对于$ u $和$ k $），因此我们可以保证（概率很高）必须存在解决方案。 $ k $ -sum的大部分吸引力，特别是与计算几何学问题的联系，都扩展到总设置。 平均案例总设置中最著名的算法是由于Wagner（遵循Blum-Kalai-Wasserman的方法），并实现了$ u^{o（1/\ log k）} $的运行时间。这击败了最差的$ k $ sum的已知（条件）下限，这提出了一个自然的问题，即是否可以进一步改进它。但是，在这项工作中，我们通过显示出最坏的晶格问题的减少来显示匹配的平均案例下限，从而将新的技术系列引入了细粒度的复杂性领域。特别是，我们表明，在$ m $元素上求解平均值$ k $ -sum $ u^{o（1/\ log k）} $上的任何算法都将在lattice问题的算法复杂性方面具有超级分析性提高。
In this work, we show the first worst-case to average-case reduction for the classical $k$-SUM problem. A $k$-SUM instance is a collection of $m$ integers, and the goal of the $k$-SUM problem is to find a subset of $k$ elements that sums to $0$. In the average-case version, the $m$ elements are chosen uniformly at random from some interval $[-u,u]$. We consider the total setting where $m$ is sufficiently large (with respect to $u$ and $k$), so that we are guaranteed (with high probability) that solutions must exist. Much of the appeal of $k$-SUM, in particular connections to problems in computational geometry, extends to the total setting. The best known algorithm in the average-case total setting is due to Wagner (following the approach of Blum-Kalai-Wasserman), and achieves a run-time of $u^{O(1/\log k)}$. This beats the known (conditional) lower bounds for worst-case $k$-SUM, raising the natural question of whether it can be improved even further. However, in this work, we show a matching average-case lower-bound, by showing a reduction from worst-case lattice problems, thus introducing a new family of techniques into the field of fine-grained complexity. In particular, we show that any algorithm solving average-case $k$-SUM on $m$ elements in time $u^{o(1/\log k)}$ will give a super-polynomial improvement in the complexity of algorithms for lattice problems.
