On query complexity measures and their relations for symmetric functions

Rajat Mittal, Sanjay S Nair, Sunayana Patro

The main reason for query model's prominence in complexity theory and quantum computing is the presence of concrete lower bounding techniques: polynomial and adversary method. Ther…