Gopalan, Parikshit ;
Servedio, Rocco A. ;
Wigderson, Avi
Degree and Sensitivity: Tails of Two Distributions
Abstract
The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely the number of Hamming neighbors of x with different fvalue). The wellknown sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivitys Boolean function can be computed by a polynomial over the reals of degree s^{O(1)}. The best known upper bounds on degree, however, are exponential rather than polynomial in s.
Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsapproximated (in l_2) by a polynomial whose degree is s * polylog(1/eps). This is the first improvement on the folklore bound of s/eps. We prove this via a new "switching lemma for lowsensitivity functions" which establishes that a random restriction of a lowsensitivity function is very likely to have low decision tree depth. This is analogous to the wellknown switching lemma for AC^0 circuits.
Our proof analyzes the combinatorial structure of the graph G_f of sensitive edges of a Boolean function f. Understanding the structure of this graph is of independent interest as a means of understanding Boolean functions. We propose several new complexity measures for Boolean functions based on this graph, including tree sensitivity and component dimension, which may be viewed as relaxations of worstcase sensitivity, and we introduce some new techniques, such as proper walks and shifting, to analyze these measures. We use these notions to show that the graph of a function of full degree must be sufficiently complex, and that random restrictions of lowsensitivity functions are unlikely to lead to such complex graphs.
We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets. We prove a lower bound on tree sensitivity in terms of decision tree depth, and show that a polynomial strengthening of this lower bound implies the robust conjecture. We feel that studying the graph G_f is interesting in its own right, and we hope that some of the notions and techniques we introduce in this work will be of use in its further study.
BibTeX  Entry
@InProceedings{gopalan_et_al:LIPIcs:2016:5848,
author = {Parikshit Gopalan and Rocco A. Servedio and Avi Wigderson},
title = {{Degree and Sensitivity: Tails of Two Distributions}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {13:113:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5848},
URN = {urn:nbn:de:0030drops58488},
doi = {10.4230/LIPIcs.CCC.2016.13},
annote = {Keywords: Boolean functions, random restrictions, Fourier analysis }
}
2016
Keywords: 

Boolean functions, random restrictions, Fourier analysis 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 