Google Research

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


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work