pith. sign in

arxiv: 1611.01029 · v2 · pith:CCOBWBAZnew · submitted 2016-11-03 · 💻 cs.CC

On the Sum of Linear Coefficients of a Boolean Valued Function

classification 💻 cs.CC
keywords functionbooleanconjecturetextvaluedwidehatalternativeasserts
0
0 comments X
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.