On the Sum of Linear Coefficients of a Boolean Valued Function

Abstract

Let $f:\{-1,1{\}}^n\to \{-1,1\}$ be a Boolean valued function having total degree $d$. Then a conjecture due to Servedio and Gopalan asserts that ${\sum }_{i=1}^n\hat{f}(i)\le {\sum }_{j=1}^d{\widehat{\text{Maj}}}_d(j)$ where ${\text{Maj}}_d$ is the majority function on $d$ bits. Here we give some alternative formalisms of this conjecture involving the discrete derivative operators on $f$.

References in corpus (1)

• Open Problems in Analysis of Boolean Functions