Please note: This seminar will take place in DC 2568 and online.
Srijita Kundu, Postdoctoral researcher
Institute for Quantum Computing
We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we also give a way to convert search problems back into partial functions. Our results include exponential separations between quantum query complexity and approximate degree (and in fact non-negative approximate degree), between approximate degree and the positive-weights adversary bound, for TFNP problems. Using our conversion between TFNP problems and partial functions, we give a partial function separation between quantum query complexity and approximate degree, thus reproving a result of Ambainis and Belovs (2023). Finally, lifting some of our results, we prove new separations in communication complexity.
Based on joint work with Shalev Ben-David.
To attend this seminar in person, please go to DC 2568. You can also attend virtually using Zoom.