论文标题

分数查询算法和轴线对准拉普拉斯的噪声敏感性

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

论文作者

Gross, Renan

论文摘要

我们介绍了经典的分数查询算法的概念,该算法概括了在平均情况下的决策树,并且可以比它们更好地表现。 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.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源