ECCC-Report TR20-020https://eccc.weizmann.ac.il/report/2020/020Comments and Revisions published for TR20-020en-usFri, 21 Feb 2020 15:58:40 +0200
Paper TR20-020
| Improved Approximate Degree Bounds For $k$-distinctness |
Shuchen Zhu,
Justin Thaler,
Nikhil Mande
https://eccc.weizmann.ac.il/report/2020/020An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants $k>2$. Specifically, the best known upper bound is $O(N^{(3/4)-1/(2^{k+2}-4)})$ (Belovs, FOCS 2012), while the best known lower bound for $k >= 2$ is $\Omega(N^{2/3} + N^{(3/4)-1/(2k)})$ (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018).
For any constant $k >= 4$, we improve the lower bound to $\Omega(N^{(3/4)-1/(4k)})$. This yields, for example, the first proof that $4$-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree.
As a secondary result, we give a simple construction of an approximating polynomial of degree $O(N^{3/4})$ that applies whenever $k <= polylog(N)$.Fri, 21 Feb 2020 15:58:40 +0200https://eccc.weizmann.ac.il/report/2020/020