Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with k-distinctness:
TR20-020 | 21st February 2020
Nikhil Mande, Justin Thaler, Shuchen Zhu

Improved Approximate Degree Bounds For $k$-distinctness

An 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 ... more >>>

ISSN 1433-8092 | Imprint