Abstract:
One can measure how complex a given boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$ is in many ways, and these different possibilities give rise to different complexity measures such as the degree $\deg(f)$ and the sensitivity $s(f)$. In 1994, Nisan and Szegedy found a polynomial upper bound for the sensitivity in terms of the degree but could not find a polynomial relation in the other direction. However, they conjectured that such a relation indeed existed and called this problem the sensitivity conjecture. Although it was originally a problem in computational complexity theory, its solution came from graph theory and was possible thanks to the so-called equivalence theorem by Gotsman and Linial, which enabled the reformulation of the conjecture in graph theoretical terms. Moreover, Hao Huang's final proof of the conjecture in 2019 is considered to be specially engaging since it mainly uses basic spectral and linear algebra techniques. Our work focuses on generalizing this story to functions $f:T^n\rightarrow T$ defined on arbitrary finite sets $T$ with cardinality $m>2$, which we call $m$-ary functions. We have obtained a polynomial upper bound for the sensitivity in terms of the degree, and we have also reformulated the sensitivity conjecture in graph theoretical terms thanks to a generalization of the equivalence theorem which is somehow more involved than the boolean one. Finally, we have generalized an interesting construction by Chung, Füredi, Graham and Seymour to obtain an infinite family of functions whose sensitivity has a specific polynomial strict upper bound in terms of the degree. This is a joint work with Ignacio García-Marco (Universidad de La Laguna) and Kolja Knauer (Universitat de Barcelona). [1] F. R. K. Chung, Z. Füredi, R. L. Graham and P. Seymour, On induced subgraphs of the cube, J. Combin. Theory Ser. A, 49 (1988), 180-187. [2] C. Gotsman and N. Linial, The equivalence of two problems on the cube, J. Combin. Theory Ser. A,61 (1992), 142-146. [3] H. Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Ann. of Math., 190 (2019), no. 3, 949-955. [4] N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity, 4 (1994), 301-313.