Jump to Content

Adversary Lower Bound for the k-sum Problem

Aleksandrs Belovs
Robert Spalek
Proceeding of 4th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS'13) (2013), pp. 323-328
Download Google Scholar

Abstract

We prove a tight quantum query lower bound Ω(n^(k/(k+1))) for the problem of deciding whether there exist k numbers among n that sum up to a prescribed number, provided that the alphabet size is sufficiently large.

Research Areas