zbMATH — the first resource for mathematics

On a Boolean maximization problem. (English) Zbl 1073.94514
Blaum, Mario (ed.) et al., Information, coding and mathematics. Proceedings of workshop honoring Professor Bob McEliece on his 60th birthday, Pasadena, CA, USA, May 24–25, 2002. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7079-9/hbk). The Kluwer International Series in Engineering and Computer Science 687, 133-140 (2002).
Summary: Among all Boolean functions \(f_j\) of \(n\) variables, \(n= 2m+1\), the \(\max_j\min_i(f_j\cdot x_i)\) value of correlation between \(f_j\) and the \(n\) independent binary variables \(x_i\), \(1\leq i\leq n\), is \({2m\choose m}\cdot 2^{-2m}\), which is uniquely achieved by \(f^* =\text{maj}(x_1,\dots,x_n)\), the majority decision function on the \(x_i\)’s. This value is asymptotically less, by a factor of \(\sqrt{\frac {\pi} {2}}\approx 1.2533\), than is achieved by the real vector \(\alpha^*\) which achieves \(\max_{|\alpha|=1}\min_i(\alpha\cdot x_i)=\frac{1} {\sqrt n}\).
For the entire collection see [Zbl 1054.94001].
94A60 Cryptography
06E30 Boolean functions