
Revised: October 12, 2020
Published: September 30, 2024
Abstract: [Plain Text Version]
For f:\{0,1\}^n \to \{0,1\} and S\subset \{1,2,\dots,n\}, let J^+_S(f) be the probability that, for x uniform from \{0,1\}^n, there is some y\in \{0,1\}^n with f(y)=1 and x\equiv y outside S. We are interested in estimating, for given \mu (f) (:= \mathbb E(f)) and m, the least possible value of \max\{J^+_S(f): |S|=m\}.
A theorem of Kahn, Kalai, and Linial (KKL) gave some understanding of this issue and led to several stronger conjectures. Here we disprove a pair of conjectures from the late 80s, as follows.
(1) The KKL Theorem implies that there is a fixed \alpha> 0 so that if \mu (f)\approx 1/2, and c> 0, then there is a set S of size at most \alpha cn with J^+_S(f) \ge 1-n^{-c}. We show that for every \delta > 0 there is an f with \mu (f)\approx 1/2 and J^+_S(f) \le 1-n^{-C} for every S of size (1/2-\delta) n, where C=C_\delta. This disproves a conjecture of Benny Chor from 1989.
(2) We also show that for fixed \gd> 0 there are c,\ga > 0 and Boolean functions f such that \mu (f) > \exp[-n^{1-c}] and J^+_S(f) \le \exp[-n^\ga] for each S of size (1/2-\gd)n. This disproves a conjecture of the third author from the late 80s.