## Analysis of Boolean Functions- 0366.4456.01

### 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

#### 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 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 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. Show that, for a given assignments A, and let G(A) be the consistency graph for A:         g(G[A]) £  g(A) + |Á|-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. Prove the theorem [RaSa] for general d, and for delta >= |F|^c (or at least for delta >= d*(|f|^c)) 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. Prove the Large Clique’s Consistency Lemma over G(A):     A large (> |Á|-½) clique in G(A) agrees almost everywhere with a single degree-r polynomial Assignment #3:   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 A1 and A2 differ on.

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