On Wagner's k-Tree Algorithm Over Integers

Haoxing Lin, Prashant Nalini Vasudevan

The k-Tree algorithm [Wagner 02] is a non-trivial algorithm for the average-case k-SUM problem that has found widespread use in cryptanalysis. Its input consists of k lists, each c…