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

Abstract

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 that the limiting run-time complexity of a natural class of these algorithms obeys the non-linear partial differential equation ${\min }_k{\partial }^{2}u/\partial x_k^2=-2$, and that the individual bit revealment satisfies the Schramm-Steif bound for Fourier weight, connecting noise sensitivity with PDEs. We discuss relations with other decision tree results.

25 pages, 3 figures