Notes of Gil Kalai’s lecture nr 1

1. Discrete Fourier analysis

Today, I state a theorem. This afternoon, Mossel explains how harmonic analysis can be used in combinatorics. The Parseval identity, though elementary, turns out to be very powerful. Tomorrow, I will give an additional ingredient, hypercontractivity.

1.1. Collective coin flipping

In 1985, Ben Or and Linial discussed a problem coming from theoretical computer science called collective coin flipping. When designing algorithms, use of random bits helps a lot. One is satisfied if the algorithm gives a correct answer with probability {>1/2}. Example (Rabin et al.) : primality test.

Even earlier, randomization arose in distributed computing. Synchronizing a large number of computers is uneasy. Assume {n} processors need to agree together on a random bit. Each processor has an access to a source of perfect random bits. The crux of the matter is that some processors are adversarial: they try to cause the process to fail. we want a procedure immune to the presence of {n/10}, or {n^{0.999}} bad processors. For this, we use a Boolean function.

1.2. Boolean functions

Definition 1 A Boolean function is a function {f:\{0,1\}^n \rightarrow \{0,1\}} (sometimes, we replace {\{0,1\}} with {\{-1,1\}}).

Here is the procedure proposed by Ben Or and Linial: Processor {i} contributes a random bit {x_i}. The collective random bit is {f(x_1,...,x_n)}. The adversarial processors can wait and see the bits sent by good processors before sending their own nasty bit. There are variants. You can allow every processor to contribute many bits. You can also precribe the order in which the bits are contributed. You can consider a protocol where every processor contributes random bits in turns.

Suggestion: Why not select at random a processor and take its bit ? Answer: We are not allowed to do this, since we are not allowed external random bits. All the randomness available belongs to individual processors.

Here are examples of Boolean functions.

  • OR (resp. AND) function {f(x_1,...,x_n)=\max\{x_1,...,x_n \}} (resp. {\min}) do not produce a uniformly distributed bit.
  • Dictatorship {f(x_1,...,x_n)=x_1} does not do the job, since one bad processor can spoil it.
  • Parity {f(x_1,..,x_n)=x_1 +...+x_n} mod {2} does not do well either, since every processor can change the output.
  • Majority {f(x_1,..,x_n)=1} if {x_1 +...+x_n > n/2}, {=0} otherwise. This can be spoiled by {\sqrt{n}} bad processors with high probability. Indeed, the fluctuations of {x_1 +...+x_n - n/2} are of size {\sqrt{n}}.

Can one do better ? Yes, this is what Ben Or and Linial observed. Before, I introduce influence.

1.3. Influence

Definition 2 (Influence) Let {f} be a Boolean function. Assume that {\mathop{\mathbb E}(f)=t} (usually, {t=1/2}). Let {S} be a set of processors. The influence of {S} towards 1 is

\displaystyle  \begin{array}{rcl}  I_S^+ =P(processors in S can force outcome 1)-t. \end{array}

The influence of {S} towards 0 is

\displaystyle  \begin{array}{rcl}  I_S^+ =P(processors in S can force outcome 0)-(1-t). \end{array}

The influence of {S} on {f} is

\displaystyle  \begin{array}{rcl}  I_S (f)=I_S^+ +I_S^-. \end{array}

It is between 0 and 1.

In case {S} has one element, {I_S^+ =I_S^-}. Notation: {I_k (f)=I_{k}(f)}. Alternatively,

\displaystyle  \begin{array}{rcl}  I_k (f)=P(\textrm{flipping }x_k\textrm{ changes the outcome}). \end{array}

Define total influence as the sum of all {I_k}‘s.

Theorem 3 (Ben Or, Linial) : For all Boolean {f} with {\mathop{\mathbb E}(f)=1/2}, the total influence

\displaystyle  \begin{array}{rcl}  I(f):=\sum_{k=1}^n I_k (f)\geq 1. \end{array}

In particular, {\max_k I_k (f)\geq 1/n}.

They realized that this is related to discrete isoperimetry ({I(f)} is also known as edge boundary or edge expansion), and follows from an inequality by Loomis and Whitney. They stressed the following questions:

  1. What can one say of the maximum influence ?
  2. Or more generally, of {\max\{I_S (f) \,;\, |S|=r\}}, especially when {r=o(n)} ?

Ben Or and Linial found Boolean functions that do better than majority for collective coin tossing.

The first example is recursive majority on triples. Let us assume that {n=3^m}. Divide recursively the populations in 3. Construct the corresponding ternary tree. Take majorities of triples at some level to assign values at the next level, then take majorities again, and so on, up to the root. (Compare with the american electoral system, with 2 levels. Soviet Union and other communist countries used to have similar systems with up to 6 levels). For this Boolean function {f}, for all {k}, {I_k (f)=n^{-log_3 (2)}}. So {I(f)=n^{1-log_3 (2)}}.

Later on, they found a better example: tribes. Let us assume that {n=ms}. Divide the population in {m} equal tribes of size {s}. Let {f=1} iff for some tribe, all the votes are 1. In other words, {f} is the OR of the ANDs of tribes. If {s=\log n -\log \log n}, then {\mathop{\mathbb P}(f=1)=1/2}. Indeed,

\displaystyle  \begin{array}{rcl}  P(\textrm{tribe says }0)=1-1/2^s, \end{array}

so

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(f=0)=\mathop{\mathbb P}(\textrm{all tribes say }0)=(1-1/2^s)^m. \end{array}

In this example, for all {k},

\displaystyle  \begin{array}{rcl}  I_k (f)=log(n)/n, \end{array}

so

\displaystyle  \begin{array}{rcl}  I(f)=log(n). \end{array}

Note the asymmetry: to force outcome 0, one needs to put an adversarial voter in each of {n/log(n)} tribes, whereas to force 1, one merely needs to fill one single tribe (of size {log(n)}) with adversaries. Recursive majority is more symmetric.

1.4. The KKL Theorem

Ben Or and Linial conjectured that one cannot do better, i.e. for every balanced Boolean function, there is a processor whose influence is at least {log(n)}.

Theorem 4 (Kahn, Kalai, Linial) For every Boolean function {f} with {\mathop{\mathbb P}(f=1)=t},

\displaystyle  \begin{array}{rcl}  \max_k I_k (f) > c. log(n)/n . \end{array}

Proof given tomorrow. It relies on some Fourier analysis, plus hypercontractivity (Bonami, Beckner, Gross). We tried many other ideas which turned out to be useless.

Corollary 5 Presence of {n/\log(n)} adversaries will fool every Boolean function.

Are there better protocols than a single Boolean function ? Answer is Yes.

The first example is passing the baton. Let the first processor select at random a second processor, which selects at random a third processor, and so on. Use the random bit proposed by the winner, the last remaining processor. This takes {n-1} rounds, {n \log(n)} random bits. What will be the strategy of adversaries ? Achieve that the winner is an adversary. For this, all they can do, when selected, is to select a good processor. This again yields a threshold of {n/\log(n)}.

N. Alon and M. Naor found a protocol with a smaller number of rounds.

Today’s record (U. Feige): Number of rounds is {log^{*}(n)}. Here is a simplified version of this protocol. Set two rooms (more rooms required to get {log^{*}(n)}). Let each processor go at random in one of the rooms. Take the room which has the smallest number of processors. Start again. There is no clear strategy for adversaries.

2. What is discrete harmonic analysis good for ?

Here is a list of questions to which the methods of discrete harmonic analysis are relevant.

2.1. Extremal combinatorics

Here are two sample results.

Sperner’s theorem (1928): An antichain of subsets of an {n}-point set has at most {choose(n,n/2)} elements. Antichain means no set contains the next. Equality holds for all subsets of size {n/2}.

Erdös-Ko-Rado theorem (1935): If F is a collection of {k}-sets in an {n}-set, {2k\leq n}, and if, for every {S}, {T\in F}, intersection is non empty, then {|F|\leq choose(n-1,k-1)}. Equality holds for {F=} all sets containing a given element.

  1. Question: What happens in case equality almost holds? e.g. if we assume {|F| \geq c.choose(n-1,k-1)}, {c} a small constant ?
  2. Question: How many large antichains are there ?
  3. Question: What if we replace pairwise non disjoint with 3-wise non disjoint ?

These questions seem to be substantially harder.

2.2. Random graphs

Subject started by Erdös and Renyi in the 1960’s. Here is a model which slightly differs from theirs, but is easier to analyze.

Given an {n}-vertex set, chose edges at random with probability {p}, get random graph {G(n,p)}.

Given a finite graph {H}, for which values of {p} will {G(n,p)} contain {H} as a subgraph, with high probability ? It clearly works for high {p}, where is the transition ?

2.3. Percolation and related models

Start with {n\times m} planar grid ({\sim 4mn} edges). Consider random subgraph obtained when every edge is taken with probability {p}. A transition arises at {p=1/2}.

  • For {p<1/2}, subgraph has only small connected components.
  • For {p=1/2}, with positive probability, left side and right side are connected.
  • For {p>1/2}, this occurs with probability 1.

Every graph property (connectedness, simply connectedness,…) is 1 or 0 depending on the assignments associated to edges (open or closed), i.e. a Boolean function.

2.4. Computational complexity

Given a Boolean function {f}, how complicated is it to compute it ? I explain the Boolean circuit model (one among many). A circuit is a directed graph split into levels. At the first level, there are Boolean variables. At the higher levels, there are gates (each of them takes several inputs and one output. The gates are chosen in the list OR, AND, NEGATION (one can get rid of NEGATION by admitting variables and their negations at the first level). Every Boolean function is an AND of ORs or an OR of ANDs, but this leads to huge circuits, so we prefer the more general class of circuits.

N/NP can be formulated as follows. The existence of a Hamiltonian cycle in an {n}-vertex graph is a Boolean function. Can it be computed by circuits of polynomial size in {n} ?

Bounding from below circuit complexity has shown to be very hard. Existing results apply only to very limited submodels. For instance, for bounded depths circuits, discrete harmonic methods are relevant.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Course, Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s