can give lower bound no better than n2,later improved to aboutn in [HJKP10].We'll present the later result,from which you can see the interesting connection to parity function.(And interestingly,it is the O(n2)upper bound of the fommula size of the parity function that is used to show this limit.) Theorem 1.2.For any convex rectangle measure u and any rectangle R f-1(1)x f-1(0),it holds that(R)≤号(n2+n). Proof.We will design a fractional partition as follows.For any I {0,1)n and any b E{0,1},define rectangle RI.b=Parityi(b)×Parityi(⑤).(Here Parityi(b)={x∈{0,1：⊕iexi=b,)We claim that R has a fractional partition R(0,1)",bE,1))each rectangle with weightb =2-(n-1). (Note that here the set is a multi-set,so some elements may appear more than once.But we count them differently.Or,an equivalent way to phrase this is that,if some rectangle appears k times,then its weight is k2-(n-1).) Indeed,for any (x,y)ER, (I,b):Parity (x)=b,Parity () =I:Parity (x)Parity (y)} =l{:Parity(x+y)≠0l =2n-1, forany x≠y. Next is the connection to the parity function.Note that rectangle Rib is actually the g1(1)x g-1(0)for g=Parity or Parity.At the end of the last lecture,we showed that the formula leafsize of Parity is at most O(n2),and mentioned that the constant can be as small as 9/8.Since u(Rb)is a lower bound ofthe leafsize.we knowthat (R(It's easy to see that negation doesn't change the leaf size of a function:L(g)=L(g).) Now we can bound u(R)from above:can give lower bound no better than 4n 2 , later improved to about 9 8 𝑛 2 in [HJKP10]. We’ll present the later result, from which you can see the interesting connection to parity function. (And interestingly, it is the O(n 2) upper bound of the formula size of the parity function that is used to show this limit.) Theorem 1.2. For any convex rectangle measure 𝜇 and any rectangle 𝑅 ⊆ 𝑓 −1(1) × 𝑓 −1 (0), it holds that 𝜇(𝑅) ≤ 9 8 (𝑛 2 + 𝑛). Proof. We will design a fractional partition as follows. For any 𝐼 ⊆ {0,1} 𝑛 and any 𝑏 ∈ {0,1}, define rectangle 𝑅𝐼,𝑏 = Parity𝐼 −1 (𝑏) × Parity𝐼 −1(𝑏̅). (Here Parity𝐼 −1 (𝑏) = {𝑥 ∈ {0,1} 𝑛:⊕𝑖∈𝐼 𝑥𝑖 = 𝑏}.) We claim that R has a fractional partition {𝑅 ∩ 𝑅𝐼,𝑏:𝐼 ⊆ {0,1} 𝑛,𝑏 ∈ {0,1}}, each rectangle with weight 𝑟𝐼,𝑏 = 2 −(𝑛−1) . (Note that here the set is a multi-set, so some elements may appear more than once. But we count them differently. Or, an equivalent way to phrase this is that, if some rectangle appears k times, then its weight is 𝑘2 −(𝑛−1) . ) Indeed, for any (𝑥,𝑦) ∈ 𝑅, |{(𝐼,𝑏):Parity𝐼 (𝑥) = 𝑏,Parity𝐼 (𝑦) = 𝑏̅}| = |{𝐼:Parity𝐼 (𝑥) ≠ Parity𝐼 (𝑦)}| = |{𝐼:Parity𝐼 (𝑥 + 𝑦) ≠ 0}| = 2 𝑛−1 , for any 𝑥 ≠ 𝑦. Next is the connection to the parity function. Note that rectangle 𝑅𝐼,𝑏 is actually the 𝑔 −1(1) × 𝑔 −1(0) for 𝑔 = Parity or Parity. At the end of the last lecture, we showed that the formula leaf size of Parity is at most O(n 2), and mentioned that the constant can be as small as 9/8. Since 𝜇(𝑅𝐼,𝑏 ) is a lower bound of the leaf size, we know that 𝜇(𝑅𝐼,𝑏 ) ≤ 9 8 𝑛 2 . (It’s easy to see that negation doesn’t change the leaf size of a function: 𝐿(𝑔) = 𝐿(𝑔̅).) Now we can bound 𝜇(𝑅) from above: