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:

Assignment #1:

  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.


Assignment #2:

  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.

Assignment #3:

  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.



Assignment #4:

  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.











 

Assignment #2:

We saw that dimension-d degree-r polynomials are alpha-codes; for which alpha? Write down the expression for the dimension-d low-degree-extension (LDE) of a string sigma in {0,1}n

  1. Show that for a boolean function f there exsits a subset I of [n] of size n/10 so that f is 1/log n far from a Junta over I
  2. Finite-Field Geometry, in 3-dimensional space: Show that 
    a. Two planes cannot intersect by only a point; They are either
    parallel or intersect by a line.
    b. For any given line l, only a |F|-1 fraction of the planes do not intersect l.
  3. Show that, for a given assignments A, and let G(A) be the consistency graph for A:

        g(G[A]) g(A) + ||-1

  1. Show that the algorithm, described in class, for clique'ing the graph:
    a. Removes at most 3*(sqrt(beta(G)))* (1/2)|G|^2 of G's edges.
    b. The resulting graph is indeed transitive.
  2. Prove the theorem [RaSa] for general d, and for delta >= |F|^c
    (or at least for delta >= d*(|f|^c))
  3. Prove the "Lemma of Large Clique":
    In a transitive graph G, whose edges are a fraction
    g of the pairs of vertices, there must be at least one clique of at least g(G)*|G| vertices.
  4. Prove the Large Cliques Consistency Lemma over G(A):
       
    A large (> ||-) clique in G(A) agrees almost everywhere with a single degree-r polynomial

Assignment #3:

  1.  
    1. Given an assignment to a longcode A:BP[R] {0, 1}, show that for any (constant) d > 0, there is a constant h(d), which depends on d revewoh R no dneped ton seod, such that:

            | {e
      R | D(Ee, A) > + d } | h(d)

      where
      D(A1, A2) is the fraction of bits A1and A2differ on.

 













Assignment #5:

  1. Assuming the Plane-vs-Plane test true, show the Point-on-Plane test true.
  2. Show a Karp-reduction from SVP to CVP (preferably deterministic, otherwise probabilistic)