Author Archive

You are currently browsing Gil Kalai’s articles.

(Gil Kalai) The entropy/influence conjecture

16 August, 2007 in guest blog, math.CA, math.PR, question | Tags: , , , , | by | 19 comments

[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 \{-1,+1\}^n be the discrete cube, i.e. the set of \pm 1 vectors (x_1,\ldots,x_n) of length n. A boolean function is any function f: \{-1,+1\}^n \to \{-1,+1\} 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 \hbox{sgn}(x_1+\ldots+x_n) returns +1 if there are more +1 variables than -1, or -1 otherwise, whereas if 1 \leq k \leq n, the “k^{th} dictator” function returns the value x_k of the k^{th} variable.

We give the cube \{-1,+1\}^n the uniform probability measure \mu (thus we assume that the n voters vote randomly and independently). Given any boolean function f and any variable 1 \leq k \leq n, define the influence I_k(f) of the k^{th} variable to be the quantity

I_k(f) := \mu \{ x \in \{-1,+1\}^n: f(\sigma_k(x)) \neq f(x) \}

where \sigma_k(x) is the element of the cube formed by flipping the sign of the k^{th} variable. Informally, I_k(f) measures the probability that the k^{th} 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

I(f) := \sum_{k=1}^n I_k(f).

Thus for instance a dictator function has total influence 1, whereas majority vote has total influence comparable to \sqrt{n}. The influence can range between 0 (for constant functions +1, -1) and n (for the parity function x_1 \ldots x_k 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 I(f) \geq 1 (with equality if and only if there is a dictatorship), whilst the Kahn-Kalai-Linial (KKL) theorem asserts that I_k(f) \gg \frac{\log n}{n} for some k. There is a result of Friedgut that if I(f) is bounded by A (say) and \varepsilon > 0, then f is within a distance \varepsilon (in L^1 norm) of another boolean function g which only depends on O_{A,\varepsilon}(1) of the variables (such functions are known as juntas).

Read the rest of this entry »

(Gil Kalai) The weak epsilon-net problem

22 April, 2007 in guest blog, math.MG, question | Tags: , , , | by | 14 comments

[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 X \subset {\Bbb R}^d be a finite set of points, and let 0 < \epsilon < 1. We say that a finite set Y \subset {\Bbb R}^d is a weak \epsilon-net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that |B \cap X| > \epsilon |X|, then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong \epsilon-net for X with respect to convex bodies.)

For example, in one dimension, if X = \{1,\ldots,N\}, and Y = \{ \epsilon N, 2 \epsilon N, \ldots, k \epsilon N \} where k is the integer part of 1/\epsilon, then Y is a weak \epsilon-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 \epsilon-net of size as small as O(1/\epsilon). Strong \epsilon-nets are of importance in computational learning theory, and are fairly well understood via Vapnik-Chervonenkis (or VC) theory; however, the theory of weak \epsilon-nets is still not completely satisfactory.

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

Now consider the situation in which X is now an arbitrary finite set, rather than a discrete cube. More precisely, let f(\epsilon,d) be the least number such that every finite set X possesses at least one weak \epsilon-net for X with respect to convex bodies of cardinality at most f(\epsilon,d). (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 \epsilon of any given territory.

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

Read the rest of this entry »

Archives