正在加载图片...
stream for A,we can use a one-way protocol to simulate it.(Since blackboard model is stronger,we can of course also use the blackboard protocol to simulate this.) Now we say that computing the d-th moment can solve the Disjnk problem.Indeed, If(y1,...,y)are pairwise disjoint,then fa(x)sn. If there is a common element in y1,...,yk,then fa(x)>kd =n+1. Therefore, cn+1)va=ck≥D(Disink)≥n(月=n(at) which gives c=Q(n1-2d). 3.Number on the Forehead We are back to total functions,i.e.the domain off is the whole X =Xx...x Xk 3.1 Cylinder intersection Let's first see what the analog of monochromatic tensors is in the NoF model.A subset C of X= X1 x...x Xk is a cylinder in the i-th dimension if C=S_ix Xi for some set S-iX-i.Namely,the membership of C doesn't depend on the i-th coordinate.A subset C of X is a cylinder intersection if CCi,where each Ci is a cylinder in dimensioni.The following theorem is an analog ofthe monochromatic rectangle/tensor decomposition in previously studied models. Theorem 3.1.Any c-bit deterministic protocol for a function fin NoF model partitions the set X into at most 2 monochromatic cylinder intersections. 3.2 Discrepancy and binary cube bound We've seen discrepancy in two-party randomized communication complexity.We can surely extend it to multiparty as well.For the sake of simplicity,let's consider the unifom case.For any Boolean function f:X{+1,-1}and any subset S of X,its discrepancy is disc,S)=☆∑xesf(xl Let's then define disc(f)=max disc(f,S),stream for A, we can use a one-way protocol to simulate it. (Since blackboard model is stronger, we can of course also use the blackboard protocol to simulate this.) Now we say that computing the d-th moment can solve the Disjn,k problem. Indeed, ⚫ If (y1, …, yk) are pairwise disjoint, then fd (x) ≤ n. ⚫ If there is a common element in y1, …, yk, then fd (𝑥) ≥ 𝑘 𝑑 = 𝑛 + 1. Therefore, c(n + 1) 1/d = 𝑐𝑘 ≥ 𝐷(𝐷𝑖𝑠𝑗𝑛,𝑘 ) ≥ Ω( 𝑛 𝑘 ) = Ω( 𝑛 (𝑛+1)1/𝑑 ) which gives c = Ω(n 1−2d). □ 3. Number on the Forehead We are back to total functions, i.e. the domain of f is the whole X = X1 × …× Xk. 3.1 Cylinder intersection Let’s first see what the analog of monochromatic tensors is in the NoF model. A subset C of X = X1 × … × Xk is a cylinder in the i-th dimension if C = S−i × Xi for some set S−i ⊆ X−i . Namely, the membership of C doesn’t depend on the i-th coordinate. A subset C of X is a cylinder intersection if C =∩i=1 k Ci , where each Ci is a cylinder in dimension i. The following theorem is an analog of the monochromatic rectangle/tensor decomposition in previously studied models. Theorem 3.1. Any c-bit deterministic protocol for a function f in NoF model partitions the set X into at most 2c monochromatic cylinder intersections. 3.2 Discrepancy and binary cube bound We’ve seen discrepancy in two-party randomized communication complexity. We can surely extend it to multiparty as well. For the sake of simplicity, let’s consider the uniform case. For any Boolean function f:X → {+1,−1} and any subset S of X, its discrepancy is disc(f, S) = 1 |X| |∑ 𝑓(𝑥) 𝑥∈𝑆 |. Let’s then define disc(f) = max S disc(f, S)
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有