A tighter bound on the number of relevant variables in a bounded degree Boolean function

2019/03/19 by Jake Wellens, Wellens, Jake · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Coding theory and cryptography #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1903.08214

Abstract

A classical theorem of Nisan and Szegedy says that a boolean function with degree d as a real polynomial depends on at most d2^d-1 of its variables. In recent work by Chiarelli, Hatami and Saks, this upper bound was improved to C ⋅ 2^d, where C = 6.614. Here we refine their argument to show that one may take C = 4.416.

Cited by

• On the Degree of Boolean Functions as Polynomials over ℤ_m

Related

• An Asymptotically Tight Bound on the Number of Relevant Variables in a\n Bounded Degree Boolean Function
• On the weight and density bounds of polynomial threshold functions
• On Separation between the Degree of a Boolean Function and the Block Sensitivity
• Degree and Sensitivity: tails of two distributions
• On Restricting No-Junta Boolean Function and Degree Lower Bounds by Polynomial Method