@inproceedings{879965d521644fce84da52846c28b239,
title = "Adversary lower bound for the k-sum problem",
abstract = "We prove a tight quantum query lower bound Ω(nk/(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.",
keywords = "knapsack packing problem, orthogonal arrays, quantum query complexity",
author = "Aleksandrs Belovs and Robert {\v S}palek",
year = "2013",
doi = "10.1145/2422436.2422474",
language = "English",
isbn = "9781450318594",
series = "ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science",
pages = "323--328",
booktitle = "ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science",
note = "2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 ; Conference date: 09-01-2013 Through 12-01-2013",
}