香港中文大学：《Theory of Computational Complexity》课程教学资源（讲义）Lecture 6 Formula complexity II

Lecture 6.Formula complexity Il 1.From Khrapchenko's bound to convex rectangle measures In the last lecture,we proved a result by Khrapchenko for any Af-1(1),B f-1(0),define S= cyW:x∈Ay∈B,lx⊕y=}and we have L()≥g-The astrcodredthe that A=f-1(1)and B=f-1(0),but convince yourself that the lower bound holds even A and B are subsets of f-1(1)and f-1(0).)We then used it to prove that L(Parityn)2n2.We of course hope to prove stronger lower bounds.So a natural question is:Can we use the same technique to prove better lower bounds?In general,understanding the power and limit ofa prevailing lower bound technique is an important task.For Khrapchenko's method,unfortunately,the answer is pretty negative:n2 is the best lower bound we can get. Exereise.Showthat for.ndas defined above,itaays holdsth IAl-BI S nz So it's a bad news.But maybe we can use a similar technique?Well,that depends on the exact definition of"similar".In this lecture,we'll investigate the power of this type of technique along one specific direction. Next we will 1.define a concept ofconvex rectangle measures 2.show that Kharpchenko's bound uses a convex rectangle measure, 3.show that all convex rectangle measures cannot give lower bounds better than 0(n2). Fix a rectangle R.Consider a function u on subrectangles ofR.(As the name suggests,a set is a subrectangle of R if it's a subset of R and it's a rectangle.)The function is a rectangle measure if it satisfies subadditive:u(R)<u(R)+u(R2),where R is partitioned into the disjoint union of R and R2,which are both rectangles themselves, ● normalized:u(R')<1 for any monochromatic subrectangle R

Lecture 6. Formula complexity II 1. From Khrapchenko’s bound to convex rectangle measures In the last lecture, we proved a result by Khrapchenko for any 𝐴 ⊆ 𝑓 −1 (1), 𝐵 ⊆ 𝑓 −1 (0), define 𝑆 = {(𝑥,𝑦): 𝑥 ∈ 𝐴, 𝑦 ∈ 𝐵,|𝑥 ⊕ 𝑦| = 1} and we have 𝐿(𝑓) ≥ |𝑆| 2 |𝐴|⋅|𝐵| . (The last lecture considered the case that 𝐴 = 𝑓 −1 (1) and 𝐵 = 𝑓 −1(0), but convince yourself that the lower bound holds even A and B are subsets of 𝑓 −1 (1) and 𝑓 −1 (0).) We then used it to prove that 𝐿(Parity𝑛 ) ≥ 𝑛 2 . We of course hope to prove strongerlower bounds. So a natural question is: Can we use the same technique to prove better lower bounds? In general, understanding the power and limit of a prevailing lower bound technique is an important task. For Khrapchenko’s method, unfortunately, the answer is pretty negative: n 2 is the best lower bound we can get. Exercise. Show that for A, B and S as defined above, it always holds that |𝑆| 2 |𝐴|⋅|𝐵| ≤ 𝑛 2 . So it’s a bad news. But maybe we can use a similar technique? Well, that depends on the exact definition of “similar”. In this lecture, we’ll investigate the power of this type of technique along one specific direction. Next we will 1. define a concept of convex rectangle measures, 2. show that Kharpchenko’s bound uses a convex rectangle measure, 3. show that all convex rectangle measures cannot give lower bounds better than 𝑂(𝑛 2 ). Fix a rectangle R. Consider a function 𝜇 on subrectangles of R. (As the name suggests, a set is a subrectangle of R if it’s a subset of R and it’s a rectangle.) The function is a rectangle measure if it satisfies ⚫ subadditive: 𝜇(𝑅) ≤ 𝜇(𝑅1 ) + 𝜇(𝑅2), where R is partitioned into the disjoint union of 𝑅1 and 𝑅2, which are both rectangles themselves, ⚫ normalized: 𝜇(𝑅′) ≤ 1 for any monochromatic subrectangle R’

One can view Khrapchenko's bound in the following way.Pick any rectangle R =A x B S (1).nboundof (Hereweused tdenotethes namely Al.|BI,the number ofentries in R.)Actually,from the proof of the theorem,we can see that what was actually showed is the following generalized fact: Theorem 1.1.For any rectangle R f-1(1)x f-1(0)and any rectangle measure u on R,we have L(f)≥(R) Now let's define convexity.Suppose R1,...,Rk are subrectangles ofR,and n,...,Tk are real numbers in [0,1]called weights.The set {Ri r:iE [k]}forms a fractional partition ofR if for any element eR.e=1.Namely,each rectangle covers a fraction ofeachentry,and the collection of these covers exactly equals to R.We will use the notation R =irRi.A rectangle measure u on R is convex if k u(R)≤ ）n(Ri) (Note that it may be a bit misleading that the name of"convexity"suggest that i=1,but actually from∑inRil=RI we know that∑in≥1 in general..) Now we proceed to the second step showing that Khrapchenko's bound is a convex rectangle measure. Khrapchenko's bound,when used on a fixed rectangle R,actually corresponds to the rectangle measure RNow we prove that the function isaonvxect casure In the proof R of the original theorem in last lecture,we already see that u is a rectangle measure.(Review the proof if this is not clear to you.)Let's prove the convexity.Suppose that {Rin:iE [k]}formsa fractional partition of R.Put Si=Sn Ri Since R =irRi,we have RI=in|Ril.And by considering eachentry,we canalso see that IS=irlSil.Therefore,we have ls2_②nlSl)2 where the inequality is by Cauchy-Schwartz Inequality. Finally,we show the most important result ofthis section:Convex rectangle measures cannot produce lower bounds better than quadratic.It was firstly proven in [KKN95]that convex rectangle measures

One can view Khrapchenko’s bound in the following way. Pick any rectangle 𝑅 = 𝐴 × 𝐵 ⊆ 𝑓 −1(1) × 𝑓 −1 (0), and one gets a lower bound of |𝑆| 2 |𝑅| . (Here we used |𝑅| to denote the size of R, namely |𝐴|⋅ |𝐵|, the number of entries in R.) Actually, from the proof of the theorem, we can see that what was actually showed is the following generalized fact: Theorem 1.1. For any rectangle 𝑅 ⊆ 𝑓 −1(1) × 𝑓 −1(0) and any rectangle measure 𝜇 on R, we have 𝐿(𝑓) ≥ 𝜇(𝑅). Now let’s define convexity. Suppose 𝑅1,…, 𝑅𝑘 are subrectangles of R, and 𝑟1 ,… , 𝑟𝑘 are real numbers in [0,1] called weights. The set {𝑅𝑖, 𝑟𝑖 :𝑖 ∈ [𝑘]} forms a fractional partition of R if for any element 𝑒 ∈ 𝑅, ∑𝑖:𝑒∈𝑅 𝑟𝑖 𝑖 = 1. Namely, each rectangle covers a fraction of each entry, and the collection of these covers exactly equals to R. We will use the notation 𝑅 = ∑𝑖 𝑟𝑖𝑅𝑖 . A rectangle measure 𝜇 on R is convex if 𝜇(𝑅) ≤ ∑𝑟𝑖𝜇(𝑅𝑖 ) k i=1 (Note that it may be a bit misleading that the name of “convexity” suggest that ∑𝑖 𝑟𝑖 = 1, but actually from ∑𝑖 𝑟𝑖 |𝑅𝑖 | = |𝑅| we know that ∑𝑖 𝑟𝑖 ≥ 1 in general.) Now we proceed to the second step showing that Khrapchenko’s bound is a convex rectangle measure. Khrapchenko’s bound, when used on a fixed rectangle R, actually corresponds to the rectangle measure 𝜇(𝑅′) = |𝑆∩𝑅 ′ | 2 |𝑅| . Now we prove that the function is a convex rectangle measure. In the proof of the original theorem in last lecture, we already see that 𝜇 is a rectangle measure. (Review the proof if this is not clear to you.) Let’s prove the convexity. Suppose that {𝑅𝑖,𝑟𝑖 :𝑖 ∈ [𝑘]} forms a fractional partition of R. Put 𝑆𝑖 = 𝑆 ∩ 𝑅𝑖 . Since 𝑅 = ∑𝑖𝑟𝑖𝑅𝑖 , we have |𝑅| = ∑ 𝑟𝑖 |𝑅𝑖 | 𝑖 . And by considering each entry, we can also see that |𝑆| = ∑ 𝑟𝑖 |𝑆𝑖 | 𝑖 . Therefore, we have 𝜇(𝑅) = |𝑆|2 |𝑅| = (∑ 𝑟𝑖 |𝑆𝑖 | i ) 2 ∑ 𝑟𝑖 |𝑅𝑖 | i ≤ ∑𝑟𝑖 |𝑆𝑖 |2 |𝑅𝑖 | i = ∑𝑟𝑖𝜇(𝑅𝑖 ) i , where the inequality is by Cauchy-Schwartz Inequality. Finally, we show the most important result of this section: Convex rectangle measures cannot produce lower bounds better than quadratic. It was firstly proven in [KKN95] that convex rectangle measures

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:

u(R)≤∑，bib4(Rb) ∥assumption of convexity ofμ =2-n-i0∑bk(Rb)∥each=2-n-0 ≤2-r-0b号2 /∥above Fact. =m2+0 where the last step follows from some basic manipulation of binomial coefficients. 2.Monotone formula size When we restrict the formula to be monotone,then we can get better lower bounds.How much better? Exponential.It's probably a bit too technical to write down full details,but we can sketchan approach. Recall that a rectangle Ax B is 1-monochromatic if there exists an i E [n],s.t.for all x E A and y E B,it holds that xi=1 and yi =0.A rectangle Ax B is 0-monochromatic if there existsan iE [n],s.t.for all xEA and yE B,it holds that xi=0 and yi 1.For monotone functions,the monotone leaf size L(f)is the minimal number of leaves of any monotone formula that computes f. Consider a rectangle R=Ax B f-1(1)x f-1(0).We associate with R a matrix MR.Formally, use a map R(R)=MR.Suppose that is linear,thus if R hasa decomposition R=iRi then so does Mg:Mg=iMg Consider all 1-monochromatic subrectangles R',which corresponds to a submatrix Mg,of Mg.If we can bound rank(Mg)sr for all 1-monochromatic subrectangles R',then we obtain a lower bound of L+(f): L+(f)≥rank(MR)/r. Actually,if R=Ri wherer=+f)and each Ri is 1-monochromatic,we have Mg= ∑=1MR.Thus rank(MR)≤∑1rank(MR)≤kr,thus L+月≥X+0=k≥rank(Mg

𝜇(𝑅) ≤ ∑ 𝑟𝐼,𝑏𝜇(𝑅𝐼,𝑏 ) 𝐼,𝑏 // assumption of convexity of μ = 2 −(𝑛−1)∑ 𝜇(𝑅𝐼,𝑏 ) 𝐼,𝑏 // each 𝑟𝐼,𝑏 = 2 −(𝑛−1) ≤ 2 −(𝑛−1)∑ 9 8 |𝐼|2 𝐼,𝑏 // above Fact. = 9 8 (𝑛 2 + 𝑛). where the last step follows from some basic manipulation of binomial coefficients. □ 2. Monotone formula size When we restrict the formula to be monotone, then we can get better lower bounds. How much better? Exponential. It’s probably a bit too technical to write down full details, but we can sketch an approach. Recall that a rectangle 𝐴 × 𝐵 is 1-monochromatic if there exists an 𝑖 ∈ [𝑛], s.t. for all 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐵, it holds that 𝑥𝑖 = 1 and 𝑦𝑖 = 0. A rectangle 𝐴 × 𝐵 is 0-monochromatic if there exists an i ∈ [n], s.t. for all 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐵, it holds that 𝑥𝑖 = 0 and 𝑦𝑖 = 1. For monotone functions, the monotone leaf size 𝐿+(𝑓) is the minimal number of leaves of any monotone formula that computes f. Consider a rectangle 𝑅 = 𝐴 × 𝐵 ⊆ 𝑓 −1(1) × 𝑓 −1 (0). We associate with R a matrix 𝑀𝑅. Formally, use a map 𝜙: 𝑅 → 𝜙(𝑅) = 𝑀𝑅. Suppose that 𝜙 is linear, thus if R has a decomposition 𝑅 = ∑𝑖𝑅𝑖 then so does 𝑀𝑅: 𝑀𝑅 = ∑ 𝑀𝑅𝑖 𝑖 . Consider all 1-monochromatic subrectangles R’, which corresponds to a submatrix 𝑀𝑅′ of 𝑀𝑅. If we can bound rank(𝑀𝑅 ′ ) ≤ 𝑟 for all 1-monochromatic subrectangles R’, then we obtain a lower bound of 𝐿+(𝑓): 𝐿+(𝑓) ≥ 𝑟𝑎𝑛𝑘(𝑀𝑅 )/𝑟. Actually, if 𝑅 = ∑ 𝑅𝑖 𝑘 𝑖=1 where 𝑟 = 𝜒+(𝑓) and each 𝑅𝑖 is 1-monochromatic, we have 𝑀𝑅 = ∑ 𝑀𝑅𝑖 𝑟 𝑖=1 . Thus 𝑟𝑎𝑛𝑘(𝑀𝑅 ) ≤ ∑ 𝑟𝑎𝑛𝑘(𝑀𝑅𝑖 ) 𝑘 𝑖=1 ≤ 𝑘𝑟, thus 𝐿+(𝑓) ≥ 𝜒+(𝑓) = 𝑘 ≥ 𝑟𝑎𝑛𝑘(𝑀𝑅 ) 𝑟

In general it's not easy to design the map with those properties.One special case is the local intersection property.For that we need to mention concepts of 1-term and 0-term for monotone functions.For any x with f(x)=1,there is a I-term(of this value)defined as a minimal subset S of fi e [n]:xi=1}s.t.if we fix the subset,then no matter how we change the variables xj outsideS, the function value remains 1.If we have more than one min-1-certificate,take one with the minimum size.Similarly we can define the 0-termas a subset S of fiE [n]:xi=1)with the minimum sizes.t. fixing variables to be 0 on the subset guarantees the function value to be 0.Note that a simple but crucial property of certificates is that for any 1-term a and 0-term b we have anb0.Indeed,if they are disjoint,then consider the input with all 1's at positions in a and all 0's at positions in b,then what are you gonna assign the function value?(No matter howyou do it,it'll violate the definition of one of the 0-and 1-term. Take a set A{1-terms;and B 0-terms).A and B locally intersect if for any bE B,there is a partition b bo Ub so that for all a E A,a intersects with exactly one of bo and bi.Definea Disjointness matrix D of dimension IAl xIBl,with rows and columns indexed by A and B, respectively.The (a,b)-entry is defined as l if anb and o if anbo0. Theorem 2.1.If A (1-terms)and B (0-terms;locally intersect,then L (f)>rank(D). Proof.It's enough to show that any 1-monochromatic subrectangle hashas rank 1.Fix a l-monochromatic subrectangle R'=A'×B,with an index is..t.any a'∈A'andb'∈B',i∈a'n b'.Partition B'into Bo UB,where Bo ={b'E B':i E bo},and B=(b'E B':iE b).Now for any a'E A'and b'E Bo,since A and B locally intersect,a'and b'intersect at exactly one ofthe bo and bi.But since iea'nb'and ie bo,we know that D(a',b)=0.Similarly,for any a'A' and b'E B,it holds that D(a',b')=1.So rank(Mg)=1. References [HJKP10]P.Hrubes,S.Jukna,A.Kulikov,and P.Pudlak.On convex complexity mesures, Theoretical Computer Science 411,1842-1854,2010. [KKN95]M.Karchmer,E.Kushilevitz,and N.Nisan:Fractional covers and communication complexity,SIAMJournal on Discrete Mathematics 8(1),76-92,1995

In general it’s not easy to design the map 𝜙 with those properties. One special case is the local intersection property. For that we need to mention concepts of 1-term and 0-term for monotone functions. For any x with 𝑓(𝑥) = 1, there is a 1-term (of this value) defined as a minimal subset S of {𝑖 ∈ [𝑛]: 𝑥𝑖 = 1} s.t. if we fix the subset, then no matter how we change the variables 𝑥𝑗 outside S, the function value remains 1. If we have more than one min-1-certificate, take one with the minimum size. Similarly we can define the 0-term as a subset S of {𝑖 ∈ [𝑛]: 𝑥𝑖 = 1} with the minimum size s.t. fixing variables to be 0 on the subset guarantees the function value to be 0. Note that a simple but crucial property of certificates is that for any 1-term a and 0-term b we have 𝑎 ∩ 𝑏 ≠ ∅. Indeed, if they are disjoint, then consider the input with all 1’s at positions in a and all 0’s at positions in b, then what are you gonna assign the function value? (No matter how you do it, it’ll violate the definition of one of the 0- and 1-term.) Take a set 𝐴 ⊆{1-terms} and 𝐵 ⊆{0-terms}. A and B locally intersect if for any 𝑏 ∈ 𝐵, there is a partition 𝑏 = 𝑏0 ∪ 𝑏1 so that for all 𝑎 ∈ 𝐴, a intersects with exactly one of 𝑏0 and 𝑏1. Define a Disjointness matrix D of dimension |𝐴| × |𝐵|, with rows and columns indexed by A and B, respectively. The (𝑎,𝑏)-entry is defined as 1 if 𝑎 ∩ 𝑏1 ≠ ∅ and 0 if 𝑎 ∩ 𝑏0 ≠ ∅. Theorem 2.1. If 𝐴 ⊆{1-terms} and 𝐵 ⊆{0-terms} locally intersect, then 𝐿+(𝑓) ≥ 𝑟𝑎𝑛𝑘(𝐷). Proof. It’s enough to show that any 1-monochromatic subrectangle has has rank 1. Fix a 1-monochromatic subrectangle 𝑅 ′ = 𝐴 ′ × 𝐵′, with an index is.t. any 𝑎 ′ ∈ 𝐴′ and 𝑏 ′ ∈ 𝐵′, 𝑖 ∈ 𝑎 ′ ∩ 𝑏 ′ .Partition B’ into 𝐵0 ′ ∪ 𝐵1 ′ , where 𝐵0 ′ = {𝑏 ′ ∈ 𝐵 ′ :𝑖 ∈ 𝑏0 ′ }, and 𝐵1 ′ = {𝑏 ′ ∈ 𝐵 ′ :𝑖 ∈ 𝑏1 ′ }. Now for any 𝑎 ′ ∈ 𝐴′ and 𝑏 ′ ∈ 𝐵0 ′ , since A and B locally intersect, a’ and b’ intersect at exactly one of the 𝑏0 ′ and 𝑏1 ′ . But since 𝑖 ∈ 𝑎 ′ ∩ 𝑏 ′ and 𝑖 ∈ 𝑏0 ′ , we know that 𝐷(𝑎’,𝑏’) = 0. Similarly, for any 𝑎 ′ ∈ 𝐴′ and 𝑏 ′ ∈ 𝐵1 ′ , it holds that 𝐷(𝑎’,𝑏’) = 1. So 𝑟𝑎𝑛𝑘(𝑀𝑅 ′) = 1. □ References [HJKP10] P. Hrubes, S. Jukna, A. Kulikov, and P. Pudlak. On convex complexity mesures, Theoretical Computer Science 411, 1842–1854, 2010. [KKN95] M. Karchmer, E. Kushilevitz, and N. Nisan: Fractional covers and communication complexity, SIAM Journal on Discrete Mathematics 8(1), 76–92, 1995