We can apply the theorem to show a lower bound for the parity function f(x)=xx2..xn Theorem 1.4.For the parity function,L(f)2n3/2 Proof.Fix all but one variable,resulting in the parity function(or its negation)ofone variable,which has leaf size at least 1.So 1≤)≤（ 3/2 L(f). which implies the claimed lower bound. Q 2.Rectangle and tiling number We now introduce another lower bound method for leaf size,due to Khrapchenko [Khr72]and Rychkov [Ryc85]. A rectangle is a pair (A,B)of disjoint sets A,B (0,1)m.A rectangle (A,B)is monochromatic if there exists an iE [n],s.t.for all xEA and y E B,it holds that xi yi.A rectangle(A,B)is 1-monochromatic if there exists an iE [n],s.t.for all x EA and y E B,it holds that xi=1 and yi=0.A rectangle (A,B)is 0-monochromatic if there exists an i E [n],s.t.for all xEA and yB, it holds that xi=0 and yi 1.Any monochromatic rectangle is either 1-or 0-monochromatic.(See why?) The tiling number x(R)of a rectangle R is the minimum number r s.t.R can be partitioned intor monochromatic rectangles.Please note that by "partition",we emphasize that the rectangles are disjoint (and,of course,their union needs to be the whole set R).The tiling numberx(f)of a function fis x(f-1(1)x f-1(0)),the tiling number ofthe rectangle f-1(1)xf-1(0) Theorem 2.1.For every Boolean function f,L(f)xf).If f is monotone,then L(f)(f). Proof.We prove the first inequality by induction on L(f),and the second one is similar.The base is easy to confirm:If L(f)=1,then f(x)=xi or f(x)=i.Then the rectangle f-1(1)xf-1(0) is itself monochromatic by definition. Now the induction step.Take a formula F with the minimal leaf size.Assume that the root is AND function;the other case can be handled similarly.So the function f=foAf,and L(f)=L(fo)+We can apply the theorem to show a lower bound for the parity function 𝑓(𝑥) = 𝑥1 ⊕ 𝑥2 ⊕ … ⊕𝑥𝑛. Theorem 1.4. For the parity function, 𝐿(𝑓) ≥ 𝑛 3/2 . Proof. Fix all but one variable, resulting in the parity function (or its negation) of one variable, which has leaf size at least 1. So 1 ≤ 𝐿(𝑓 ′) ≤ ( 1 𝑛 ) 3/2 𝐿(𝑓), which implies the claimed lower bound. □ 2. Rectangle and tiling number We now introduce another lower bound method for leaf size, due to Khrapchenko [Khr72] and Rychkov [Ryc85]. A rectangle is a pair (A,B) of disjoint sets 𝐴, 𝐵 ⊆ {0,1} 𝑛. A rectangle (A,B) is monochromatic if there exists an i ∈ [n], s.t. for all 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐵, it holds that 𝑥𝑖 ≠ 𝑦𝑖 . A rectangle (A,B) is 1-monochromatic if there exists an i ∈ [n], s.t. for all x ∈ A and y ∈ B, it holds that 𝑥𝑖 = 1 and 𝑦𝑖 = 0. A rectangle (A,B) is 0-monochromatic if there exists an i ∈ [n], s.t. for all 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐵, it holds that 𝑥𝑖 = 0 and 𝑦𝑖 = 1. Any monochromatic rectangle is either 1- or 0-monochromatic. (See why?) The tiling number 𝜒(𝑅) of a rectangle R is the minimum number r s.t. R can be partitioned into r monochromatic rectangles. Please note that by “partition”, we emphasize that the rectangles are disjoint (and, of course, their union needs to be the whole set R). The tiling number 𝜒(𝑓) of a function f is χ(𝑓 −1(1) × 𝑓 −1(0)), the tiling number of the rectangle 𝑓 −1(1) × 𝑓 −1(0). Theorem 2.1. For every Boolean function f, 𝐿(𝑓) ≥ 𝜒(𝑓). If f is monotone, then 𝐿+(𝑓) ≥ 𝜒+(𝑓). Proof. We prove the first inequality by induction on L(f), and the second one is similar. The base is easy to confirm: If 𝐿(𝑓) = 1, then 𝑓(𝑥) = 𝑥𝑖 or 𝑓(𝑥) = 𝑥̅𝑖 . Then the rectangle 𝑓 −1(1) × 𝑓 −1(0) is itself monochromatic by definition. Now the induction step. Take a formula F with the minimal leaf size. Assume that the root is AND function; the other case can be handled similarly. So the function 𝑓 = 𝑓0 ∧ 𝑓1 , and 𝐿(𝑓) = 𝐿(𝑓0 ) +