Noise sensitivity from fractional query algorithms and the axis-aligned Laplacian
share
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∂^2u/∂ 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.
READ FULL TEXT