English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this work, we show the first worst-case to average-case reduction for theclassical $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 thatsums to $0$. In the average-case version, the $m$ elements are chosen uniformlyat random from some interval $[-u,u]$.  We consider the total setting where $m$ is sufficiently large (with respectto $u$ and $k$), so that we are guaranteed (with high probability) thatsolutions must exist. Much of the appeal of $k$-SUM, in particular connectionsto 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 forworst-case $k$-SUM, raising the natural question of whether it can be improvedeven further. However, in this work, we show a matching average-caselower-bound, by showing a reduction from worst-case lattice problems, thusintroducing a new family of techniques into the field of fine-grainedcomplexity. 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-polynomialimprovement in the complexity of algorithms for lattice problems.

On the Hardness of Average-case k-SUM