Analysis of Boolean Functions - 0366.4456.01

Fall Semester 2002/3: Thursday 15-18, Schreiber 006

Instructor: Muli Safra

T.A.: Oded Schwartz

The course would cover advanced topics concerning analysis of Boolean functions, and application of it to various fields such as: Scoial Choice and voting systems, first passage percolation, Complexity theory, in particular hardness of approxiamtion problems.

Lectures:

Introduction: Influence of variables, Norms (expectation & sum), Fourier Transform. Voting systems: Dictatorship, Junta (Triangle Inequality [Minkovsky], monotonicity)

Preliminaries: Fourier Transform Parity-Functions/Characters; Dictatorships; Influence, Junta, Average-Sensitivity; High/Low Frequencies

Connections: Linear functions, [FKN]: Almost-linear Boolean Functions are Shallow

Tests: Linearity, Long-code, Monotonicity

Junta Test

Beckner inequality: Friedgut Theorem,

Learning Juntas

KKL, Symmetric Graph Properties

First Passage Percolation

Extended FKN

Hardness of Vertex-Cover

Noise-insensitive boolean functions are juntas

Isoperimetric Inequlities; Poincare Inequalities

 

Presentations:

Influence of variables, Norms (expectation & sum), Fourier Transform. Dictatorship, Junta

Assignments:

1. Prove Parseval's formula
2. Show that the set of all (not necessarily boolean) multiplicative functions f on the hyper-cube so that f(\emptyset) \noteq 0 is exactly the set of characters on the hyper-cube.
   
   Due October 24.

1. Let f_i be the following boolean function on the cube:
   f_i(x)=1 - x_i

   Show that delta_M(f_i)/epsilon_M(f_i) = 2/n

   
   
   Due November 14.

1. Let T(f) be the following test:
   Choose a random x from {0,1}^n, and z from B(n,(1-delta)/2). Accept if f(x)=f(x xor z), and reject otherwise.

   Show a function f (which is not a long-code or the constant function) that passes the test with probability > delta, but is not close to any junta of constant j(delta) size.

2. Prove the following Chernoff's bound:
   If X~B(n.p) then
   Pr[X>(1+d)E[X]] < e^(-E[X]*d^2/4)
   
   

3. Show the following properties for parity function f:
   a. delta_M(f)=1/2
   b. 1/2-o(1) <= epsilon_M(f) <= 1/2
   Hint: Consider maximal matching between any two layers that contradict monotonicity. Bound the unmatched vertices in each layer using Hall's theorem. Sum up, and recall that (n choose n/2) = O(2^n/ n^0.5).
   
   Due December 5.

1. Let \mue_f(p) = Pr _{x \in \mue_p }[f(x)>0].
   Show that if f(x) is monotone (in x) then \mue_f(p) is monotone (in p).
   
   

2. Give an example of a function f which has a linear average sensitivity but is at least epsilon far from any constant size junta.

3. Do test hold under the biased distribution \mue_p ?
   a. Give counter examples for the long-code and linearity tests
   b. Prove the junta test under this distribution.

   
   

   
   Due December 19.

Assignment #2:

1. Prove that for p >= r ||f||p >= ||f||r
2. Show that for a montone boolean function f influencei(f) = | \hat f ({i}) |
3. Show that the average sesitivity of a balanced (half -1 and half 1) boolean function is at least 1.
4. Given a boolean function f, show that if, for random x and y's, the probability that
   f(x)f(y)=f(x XOR y) is close to 1 then f is close to a character.
5. For real funtions f and g, define f*g(x)=EXPECTAION_y f(y)g(x XOR y).
   a. Write down the Fourier expansion of f*g in terms of the expansions of f and of g.
   b. Find for any \delta, a function g_\delta s.t. T_\delta[f] = f*g_\delta.
   
6. Show that, for a monotone family F of subsets, mu_q(F) is monotone non-decreasing in q
7. Describe an (epsilon, j)-junta with the highest average-sensitivity - both monotone and non-monotone
8. Show that Friedgut's theorem is optimal up to a constant factor in the exponent (namely, describe a family of subsets, which can be epsilon-approximated by a j-junta only for j roughly as large as in the theorem)
9. Two families of subsets F1, F2 are said to be cross-intersecting if every subset of F1 intersects every subset of F2.
   Show that, for any q<=1/2, mu_q(F1)+mu_q(F2) > 1 implies F1, F2 are not cross-intersecting
10. Prove Russo's lemma.
11. Prove that once showing \bar B[I] is of non-negligible size, there exists q in [p,p+gamma] s.t. a non-negligible fraction of \bar B[I] have small, < 1/gamma, average-sensitivity with respect to mu_q
12. Show, for every p, there may be an independent-set of size P-dot in the graph H
13. Show that the relative size of the core-family of B, CF[B], is only O(delta) far from that of I[B]
14. Prove that: given a family of subsets F over [n], and t elements C of [n] each of influence < eta on F; let F' be the family of all subsets of F that do not intersect C; then mu^{[n]\C}(F') >= mu^{[n]}(F)-eta*2^{-O(t)}, namely, the weight of F' within the powerset of [n]\C is almost at least as large as the weight F within the powerset of [n]
    
    Due May 21.