A tighter bound on the number of relevant variables in a bounded degree Boolean function
classification
💻 cs.DM
keywords
booleanbounddegreefunctionvariablesargumentboundedcdot
read the original 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 \cdot 2^d$, where $C = 6.614$. Here we refine their argument to show that one may take $C = 4.416$.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Classes Testable with $O(1/\epsilon)$ Queries for Small $\epsilon$ Independent of the Number of Variables
k-juntas, low-degree Fourier functions, and sparse polynomials are testable with O(1/ε) queries independent of n for small ε.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.