Noise sensitivity from fractional query algorithms and the axis-aligned Laplacian

Renan Gross

We introduce the notion of classical fractional query algorithms, which generalize decision trees in the average-case setting, and can potentially perform better than them. We show…