| Title | : | Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps |
| Speaker | : | Krishnamoorthy Dinesh (IIT Madras) |
| Details | : | Tue, Jan 30, 2018 4:00 PM, @ Turing Hall |
| Abstract | : | For a Boolean function, a combinatorial parameter of interest is the sensitivity defined as the maximum number of bit flips (for any input) that can change the function value over all inputs. An algebraic parameter of interest is the degree of a Boolean function which is the degree of the real multilinear polynomial that agree with the function on Boolean inputs. Nisan and Szegedy (1992) conjectured that for every Boolean function, the degree of the function is at most polynomial in its sensitivity which is now called as the Sensitivity Conjecture. From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function f, the communication complexity of a related function F(x,y) defined as f(x oplus y) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f in the Fourier expansion of f).
A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures, it suffices to upper bound alternation of any Boolean function by a polynomial in sensitivity and logarithm of sparsity, respectively. We show that there exists a family of Boolean functions for which alternation is at least exponential in sensivity and alternation is at least exponential in log-sps(f). Despite this exponential gap, we show that both the conjectures are true for functions with the alternation upper bounded by poly(log n). Enroute the proof, we derive new relationship between deg(f), deg_2(f) and alternation of any Boolean function. We show more applications of this new relation. This is joint work with Jayalal Sarma (IITM), and is to appear in CALDAM 2018. |