The Quantumly Fast and the Classically Forrious

Clément L. Canonne, Kenny Chen, Julián Mestre

We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\text{forr}(f,g)=1$ or $\textrm{forr}(f…