ๆญฃๅœจๅŠ ่ฝฝๅ›พ็‰‡...
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 ๐ฟ+(๐‘“) โ‰ฅ ๐œ’+(๐‘“) = ๐‘˜ โ‰ฅ ๐‘Ÿ๐‘Ž๐‘›๐‘˜(๐‘€๐‘… ) ๐‘Ÿ
<<ๅ‘ไธŠ็ฟป้กตๅ‘ไธ‹็ฟป้กต>>
©2008-็Žฐๅœจ cucdc.com ้ซ˜็ญ‰ๆ•™่‚ฒ่ต„่ฎฏ็ฝ‘ ็‰ˆๆƒๆ‰€ๆœ‰