On the Sum of Linear Coefficients of a Boolean Valued Function
classification
💻 cs.CC
keywords
functionbooleanconjecturetextvaluedwidehatalternativeasserts
read the original abstract
Let $f:\{-1,1\}^{n}\rightarrow \{-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}\widehat{f}(i)\leq \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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.