1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't quite understand the question as it is stated. Are you asking whether for any subset $A\subset\{-1,1\}^n$ with $|A|=2^{n-1}$ there is a half-space $P:=\{x\in\{-1,1\}^n \colon L(x)>0\}$, where $L$ is a linear, homogeneous, $n$-variate polynomial, such that $A$ has at least $51\%$ of its points inside $P$? $\endgroup$
    – Seva
    Jan 9, 2022 at 20:48
  • $\begingroup$ Yes, we can rephrase the question like this. $\endgroup$
    – Dattier
    Jan 9, 2022 at 23:09

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Can you explain why the xor is a contre example? $\endgroup$
    – Dattier
    Jan 10, 2022 at 9:41
  • $\begingroup$ @Dattier The XOR function is noise sensitive (since the value of the function is uncorrelated with its value after replacing one variable with a random bit) so Theorem 1.7 in [1] yields the claim. $\endgroup$ Jan 11, 2022 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.