On the Fine-Grained Query Complexity of Symmetric Functions

Supartha Podder, Penghui Yao, Zekun Ye

This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to $1/2$. Our con…