6533b86dfe1ef96bd12ca026
RESEARCH PRODUCT
Adversary Lower Bound for the k-sum Problem
Aleksandrs BelovsRobert Spaleksubject
FOS: Computer and information sciencesDiscrete mathematicsQuantum queryQuantum PhysicsFOS: Physical sciencesComputational Complexity (cs.CC)AdversaryOmegaUpper and lower boundsCombinatoricsComputer Science - Computational ComplexityOrthogonal arrayAlphabetQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata TheoryMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-01-09 |