Recognition: unknown
Adversary Lower Bound for the k-sum Problem
classification
🪐 quant-ph
cs.CC
keywords
boundlowerproblemadversaryalphabetarxivauthorsdeciding
read the original abstract
We prove a tight quantum query lower bound $\Omega(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. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Tight Quantum Lower Bound for k-Distinctness
A new quantum lower bound framework proves a tight bound for k-Distinctness.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.