2018/01/25 by John Chiarelli, Pooya Hatami, Chiarelli, John +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1801.08564
openalex publication_date 2018/01/25 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We prove that there is a constant C\≤ 6.614 such that every Boolean\nfunction of degree at most d (as a polynomial over \ℝ) is a C\⋅\n2d-junta, i.e. it depends on at most C\⋅ 2d variables. This improves\nthe d\⋅ 2d-1 upper bound of Nisan and Szegedy [Computational Complexity\n4 (1994)]. Our proof uses a new weighting scheme where we assign weights to\nvariables based on the highest degree monomial they appear on.\n The bound of C\⋅ 2d is tight up to the constant C as a lower bound of\n2d-1 is achieved by a read-once decision tree of depth d. We slightly\nimprove the lower bound by constructing, for each positive integer d, a\nfunction of degree d with 3\⋅ 2d-1-2 relevant variables. A similar\nconstruction was independently observed by Shinkar and Tal.\n