An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function

John Chiarelli, Pooya Hatami, Michael Saks

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We prove that there is a constant C ≤ 6.614 such that every Boolean function of degree at most d (as a polynomial over ℝ) is a C·2d-junta, i.e., it depends on at most C·2d variables. This improves the d·2d-1 upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)]. The bound of C·2d is tight up to the constant C, since a read-once decision tree of depth d depends on all 2d - 1 variables. We slightly improve this lower bound by constructing, for each positive integer d, a function of degree d with 3·2d-1 - 2 relevant variables. A similar construction was independently observed by Shinkar and Tal.

Original languageEnglish (US)
Pages (from-to)237-244
Number of pages8
JournalCombinatorica
Volume40
Issue number2
DOIs
StatePublished - Apr 1 2020

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function'. Together they form a unique fingerprint.

Cite this