The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and a little later I will explain further the notions I am using.
Conjecture 1: Let be a monotone Boolean function described by monotone threshold circuits of size M and depth D. Then is stable to (1/t)-noise where .
Conjecture 2: Let be a monotone Boolean function described by a threshold circuits of size M and depth D. Then is stable to (1/t)-noise where .
The constant 100 in the exponent is, of course, negotiable. In fact, replacing with any function of will be sufficient for the applications we have in mind. The best we can hope for is that the conjectures are true if behaves like .
Conjecture 1 is plausible but it looks difficult. The stronger Conjecture 2 while tempting is quite reckless. Note that the conjectures differ “only” in the location of the word “monotone”. Continue reading