The Compressed Oracle Method in Quantum Complexity and Cryptography

The compressed oracle technique, introduced in by Zhandry in 2019, is a technique for analyzing quantum query algorithms that has led to a number of breakthroughs in quantum complexity theory and cryptography. In this mini-workshop, we will hear about recent applications of this technique and variants to quantum query complexity and to the study of quantum pseudorandom unitaries. The goal of this week will be to better understand the power of this technique relative to traditional workhorses in quantum query complexity such as the polynomial method and the adversary method, and to identify directions for future work.