We can use this to show a quadratic lower bound for parity function,improving the bound given in the last section. Theorem 2.3.Let f be the parity function ofn variables.Then L(f)>n2. Proof.Clearly,IAl IBl 2n-1,and ISl n2n-1.So L(f)>n2. One may wonder whether this lower bound can be further improved.The answer is no:actually there is a formula to compute parity function with O(n2)leaves.Can you find one? (hint:Consider the two-variable version,x1x2first.) References [Sub61]B.A.Subbotovskaya,Realizations of linear functions by formulas using +,.,-Soviet Math.Dokl.2.110-112.1961 [Khr72]V.M.Khrapchenko,A method of obtaining lower bounds for the complexity of nt-schemes,Math.Notes Acad.ofSci.USSR 10,474-479,1972 [Ryc85]K.L.Rychkov,A modification of Khrapchenko's method and its application to lower bounds for-schemes of code functions,in Metody Diskretnogo Analiza,42 (Novosibirsk),91-98, 1985.We can use this to show a quadratic lower bound for parity function, improving the bound given in the last section. Theorem 2.3. Let f be the parity function of n variables. Then 𝐿(𝑓) ≥ 𝑛 2 . Proof. Clearly, |A| = |B| = 2 n−1 , and |S| = n2 n−1 . So 𝐿(𝑓) ≥ 𝑛 2 . □ One may wonder whether this lower bound can be further improved. The answer is no: actually there is a formula to compute parity function with O(n 2 ) leaves. Can you find one? (hint: Consider the two-variable version, 𝑥1 ⊕ 𝑥2, first.) References [Sub61] B. A. Subbotovskaya, Realizations of linear functions by formulas using +, ., -, Soviet Math. Dokl. 2, 110–112, 1961. [Khr72] V.M. Khrapchenko, A method of obtaining lower bounds for the complexity of 𝛑-schemes, Math. Notes Acad. of Sci. USSR 10, 474–479, 1972. [Ryc85] K. L. Rychkov, A modification of Khrapchenko’s method and its application to lower bounds for -schemes of code functions, in Metody Diskretnogo Analiza, 42 (Novosibirsk), 91–98, 1985