2024/09/24 by Sara Asensio, Asensio, Sara, Ignacio García-Marco +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2409.16141
openalex publication_date 2024/09/24 · openalex created_date 2024/10/26 · openalex updated_date 2026/07/28
The study of complexity measures of Boolean functions led Nisan and Szegedy to state the sensitivity conjecture in 1994, claiming a polynomial relation between degree and sensitivity. This problem remained unsolved until 2019, when Huang proved the conjecture via an equivalent graph theoretical reformulation due to Gotsman and Linial. We study m-ary functions, i.e., functions f: Tn → T where T⊆ ℂ is a finite alphabet of cardinality |T| = m and extend the notions of degree deg(f) and sensitivity s(f) to m-ary functions and show s(f)∈ O(deg(f)2). This generalizes results of Nisan and Szegedy. Conversely, we introduce the m-ary sensitivity conjecture, claiming a polynomial upper bound for deg(f) in terms of s(f). Analogously to results of Gotsman and Linial, we provide a formulation of the conjecture in terms of imbalanced partitions of Hamming graphs into low degree subgraphs. Combining this with ideas of Chung, Füredi, Graham and Seymour, we show that for any prime p the bound in the p-ary sensitivity conjecture has to be at least quadratic: there exist p-ary functions f of arbitrarily large degree and deg(f)∈ Ω(s(f)2).