Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR15-131 | 10th August 2015 23:09

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

TR15-131
Authors: Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson
Publication: 12th August 2015 04:39
Keywords:

Abstract:

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can be computed by a shallow decision tree. While this conjecture implies that smooth functions are easy to compute in the simplest computational model, to date no non-trivial upper bounds were known for such functions in any computational model, including unrestricted Boolean circuits. Even a bound on the description length of such functions better than the trivial \$2^n\$ does not seem to have been known.

In this work, we establish the first computational upper bounds on smooth Boolean functions:

1) We show that every sensitivity \$s\$ function is uniquely specified by its values on a Hamming ball of radius \$2s\$. We use this to show that such functions can be computed by circuits of size \$n^{O(s)}\$.

2) We show that sensitivity \$s\$ functions satisfy a strong pointwise noise-stability guarantee for random noise of rate \$O(1/s)\$. We use this to show that these functions have formulas of depth \$O(s\log n)\$.

3) We show that sensitivity \$s\$ functions can be (locally) self-corrected from worst-case noise of rate \$\exp(-O(s))\$.

All our results are simple, and follow rather directly from (variants of) the basic fact that the function value at few points in small neighborhoods of a given point determine its function value via a majority vote. Our results confirm various consequences of the conjecture. They may be viewed as providing a new form of evidence towards its validity, as well as new directions towards attacking it.

ISSN 1433-8092 | Imprint