| On k-wise independent distributions and Boolean functions (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We pursue a systematic study of the following problem. Let f: {0, 1} n → {0, 1} be a (usually monotone) boolean function whose behaviour is well understood when the input bits are identically independently distributed. What can be said about the behaviour of the function when the input bits are not completely independent, but only k-wise independent, i.e. every subset of k bits is independent? more precisely, how high should k be so that any k-wise independent distribution ”fools ” the function, i.e. causes it to behave nearly the same as when the bits are completely independent? In this paper, we are mainly interested in asymptotic results about monotone functions which exhibit sharp thresholds, i.e. there is a critical probability, pc, such that P (f = 1) under the completely independent distribution with marginal p, makes a sharp transition, from being close to 0 to being close to 1, in the vicinity of pc. For such (sequences of) functions we define 2 notions of ”fooling”: K1 is the independence needed in order to force the existence of the sharp threshold (which must then be at pc). K2 is the independence needed to ”fool ” the function at pc. In order to answer these questions, we explore the extremal properties of k-wise independent distributions and provide ways of constructing such distributions. These constructions are connected to linear error correcting codes. We also utilize duality theory and show that for the function f to behave (almost) the same under all k-wise independent inputs is equivalent to the function f being well approximated by a real polynomial in a certain fashion. This type of approximation is stronger than approximation in L1. We analyze several well known boolean functions (including AND, Majority, Tribes and Percolation among others), some of which turn out to have surprising properties with respect to these questions. In some of our results we use tools from the theory of the classical moment problem, seemingly for the first time in this subject, to shed light on these questions. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||