| Title | : | Alternation, Degree and Sensitivity : New Bounds and Super-linear Gaps |
| Speaker | : | Krishnamoorthy Dinesh (IITM) |
| Details | : | Tue, 29 Aug, 2017 2:00 PM @ Alan Turing Hall |
| Abstract: | : | Often while solving computational problems, we would want to understand how ``sensitive'' the solution is to changes in the input instance. Abstracting the computational problem as a Boolean function, the sensitivity (denoted ​s​(f)) is defined to be the number of input bits (maximized over all input settings) which if flipped, changes the value of the function. If instead of a single bit, we allow a block of bits to be flipped and we want to count the maximally disjoint such blocks, we
get to a notion called block sensitivity (denoted bs​(​f)). Nisan and Szegedy (1992) conjectured that for every Boolean function $f$, the block sensitivity is upper bounded polynomially by sensitivity. Attempts to resolve this conjecture, popularly called as the ​​sensitivity ​conjecture, has led to the discovery of connections between several other parameters of Boolean functions.
In this ​work, we show new relations and establish gaps between the Boolean function parameters -- alternation, sensitivity, degree and F_2-degree of Boolean function f denoted alt(f), s(f), deg(f) and F_2-def(f) respectively. A motivation for this study is the recent result of Lin and Zhang (2016) who showed that the Sensitivity Conjecture holds for Boolean functions whose alternation is upper bounded by polynomial in sensitivity. ​(1) We show that there exists a family of Boolean functions for which alt(f) is super-linear in s(f), alt(f) is super-linear in deg(f) and s(f) is super-linear in F_2-deg(f). The main tool used is a bound on alternation of composed Boolean functions.​ ​En-route the above proof, we show that for any Boolean function f, there exists a linear transform L such that alt(f) is at most 2s(g)+1 where g(x) is f(L(x)). ​(2) We ​use​ th​e the arguments in Lin and Zhang (2016) implies that for any Boolean function f, deg(f) is at most alt(f)​ x F_2-deg(f)^2. As two quick applications, we answer a question of Kulkarni and Santha (2013) on asymptotically bounding logarithm of sparsity of monotone Boolean functions by its degree and we improve a bound on influence of Boolean functions by Guo and Komargodski (2017). |
