Results on sensitivity, composition, the tournament predicates and the separation, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Disjoint ORs — Lemma 2.1. For the OR of m disjoint copies of P: s_0 is at most m s_0(P), s_1 is at most s_1(P), and if P(0) = 0 the block sensitivity at zero is at least m bs(P, 0).
• A quadratic example (Rubinstein) — Proposition 3.1. The OR of k copies of the exact-pair function on 2k bits has sensitivity 2k and block sensitivity at least k^2.
• Composition — Lemma 4.1. s(f o g) <= s(f) s(g); if g(0) = 0, then bs(f o g, 0) >= bs(f, 0) bs(g, 0).
• Powering — Proposition 4.2. A function with f(0) = 0, s(f) <= A and bs(f, 0) >= B > A^2 > 1 gives, by repeated composition, functions with bs >= s^alpha, alpha = log B / log A > 2, and bs at zero tending to infinity.
• Labels on a tournament — Lemma 1.1. The edges of the regular tournament on 2M^2 + 1 rows can be labelled from [ceil(sqrt M)] so that no 16 rows admit positions m_j matching every label inside them.
• Clauses and nesting — Lemma 3.1. The conditions of a clause concern distinct children, so one flip changes at most one of them; the predicates of each level are nested.
• Blocks at zero — Lemma 4.1. At level l all predicates vanish at zero and have M k^l common disjoint sensitive blocks of size L r^l.
• Level zero — Lemma 5.1. The Hamming-ball predicates have S_0 <= L, S_1 <= LM and no joint sensitivity.
• Sensitivity recurrences — Proposition 1.1. S_1 <= M^2 S'_0 + r S'_1, J_1 <= M^2 J'_0 + r S'_1, S_0 <= t S'_0 + S'_1 + 3 J'_1, J_0 <= t S'_0 + 3 J'_1.
• Growth of the profiles — Lemma 2.1. If M >= 9^(d+1), then S_(l,b) <= 2 L M^(l+b) for all levels l <= d.
• Block sensitivity versus sensitivity squared (OpenAI) — Theorem 3.1. For every C > 0 there is a nonconstant Boolean function with bs(f) > C s(f)^2; for every d >= 1 one with bs(f)/s(f)^2 >= 2^d / (4 (d+2)^2).
• A power separation — Corollary 3.2. There are alpha > 2 and nonconstant Boolean functions F_m with bs(F_m, 0) >= s(F_m)^alpha and bs(F_m, 0) tending to infinity.

Reading order

Read the lessons in order. The first introduces the measures and the tools for combining functions. The second constructs the predicates. The third proves the recurrences and the theorem.