(Gil Kalai) The entropy/influence conjecture

[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. – T.]

The entropy-influence conjecture seeks to relate two somewhat different measures as to how a boolean function has concentrated Fourier coefficients, namely the total influence and the entropy.

We begin by defining the total influence. Let be the discrete cube, i.e. the set of vectors of length n. A boolean function is any function from the discrete cube to {-1,+1}. One can think of such functions as “voting methods”, which take the preferences of n voters (+1 for yes, -1 for no) as input and return a yes/no verdict as output. For instance, if n is odd, the “majority vote” function returns +1 if there are more +1 variables than -1, or -1 otherwise, whereas if , the “ dictator” function returns the value of the variable.

We give the cube the uniform probability measure (thus we assume that the n voters vote randomly and independently). Given any boolean function f and any variable , define the influence of the variable to be the quantity

where is the element of the cube formed by flipping the sign of the variable. Informally, measures the probability that the voter could actually determine the outcome of an election; it is sometimes referred to as the Banzhaf power index. The total influence I(f) of f (also known as the average sensitivity and the edge-boundary density) is then defined as

Thus for instance a dictator function has total influence 1, whereas majority vote has total influence comparable to . The influence can range between 0 (for constant functions +1, -1) and n (for the parity function or its negation). If f has mean zero (i.e. it is equal to +1 half of the time), then the edge-isoperimetric inequality asserts that (with equality if and only if there is a dictatorship), whilst the Kahn-Kalai-Linial (KKL) theorem asserts that for some k. There is a result of Friedgut that if is bounded by A (say) and , then f is within a distance (in norm) of another boolean function g which only depends on of the variables (such functions are known as juntas).

(Gil Kalai) The weak epsilon-net problem

[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. – T.]

This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points. More precisely, we fix a dimension d and make the following definition (introduced by Haussler and Welzl):

• Definition: Let be a finite set of points, and let . We say that a finite set is a weak -net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that , then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong -net for X with respect to convex bodies.)

For example, in one dimension, if , and where k is the integer part of , then Y is a weak -net for X with respect to convex bodies. Thus we see that even when the original set X is very large, one can create a -net of size as small as . Strong -nets are of importance in computational learning theory, and are fairly well understood via Vapnik-Chervonenkis (or VC) theory; however, the theory of weak -nets is still not completely satisfactory.

One can ask what happens in higher dimensions, for instance when X is a discrete cube . It is not too hard to cook up -nets of size (by using tools such as Minkowski’s theorem), but in fact one can create -nets of size as small as simply by taking a random subset of X of this cardinality and observing that “up to errors of “, the total number of essentially different ways a convex body can meet X grows at most polynomially in . (This is a very typical application of the probabilistic method.) On the other hand, since X can contain roughly disjoint convex bodies, each of which contains at least of the points in X, we see that no -net can have size much smaller than .

Now consider the situation in which X is now an arbitrary finite set, rather than a discrete cube. More precisely, let be the least number such that every finite set X possesses at least one weak -net for X with respect to convex bodies of cardinality at most . (One can also replace the finite set X with an arbitrary probability measure; the two formulations are equivalent.) Informally, f is the least number of “guards” one needs to place to prevent a convex body from covering more than of any given territory.

• Problem 1: For fixed d, what is the correct rate of growth of f as ?