Let $f$ be a balanced Boolean function.



> 
> Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
> 
> 
> 


$g (x) = a\_1 (2x\_1-1) + ... + a\_n (2x\_n-1)$ and the $a\_i$ reals.


Ps : if the answer is yes, then NP=P.



Boolean function : approximation by a linear function
The answer is no. In fact, noise sensitive functions are characterized by being asymptotically uncorrelated with all weighted majority functions.
See Theorem 1.7 in [1]. A simple example of a noise sensitive function is the xor of all the Boolean variables. A more interesting example is percolation, see section 4 of [1].


[1] Benjamini, Itai, Gil Kalai, and Oded Schramm. "Noise sensitivity of Boolean functions and applications to percolation." Publications Mathématiques de l'Institut des Hautes Études Scientifiques 90, no. 1 (1999): 5-43. <https://link.springer.com/content/pdf/10.1007/BF02698830.pdf>


