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.