Nikhil S. Mande

Quantum Query Complexity of Maximum Degree and its Generalizations

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\Theta(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a...