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

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{\mathrm{\partial }}^{2}u\mathrm{/}\mathrm{\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.