论文标题
分数查询算法和轴线对准拉普拉斯的噪声敏感性
Noise sensitivity from fractional query algorithms and the axis-aligned Laplacian
论文作者
论文摘要
我们介绍了经典的分数查询算法的概念，该算法概括了在平均情况下的决策树，并且可以比它们更好地表现。 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 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.
