2.Number in Hand,with a blackboard. 2.1 From rectangle to tensor The counterpart ofrectangle in NiH case is tensor.A tensor in X=Xx...x Xk is a set S= S x...x Sk where SiE Xi.The following is a straightforward generalization of the rectangle property Proposition 2.1.Any c-bit deterministic protocol for a function f in NiH model partitions the set X at most into 2 monochromatic tensors. We sometimes consider partial functions,which are functions with domain not the entire X but only a subset of it.Equivalently,we can imagine that there is a promise that the input comes from a fixed subset of X.For inputs that fall outside the subset,we don't care.A protocol is correct for this partial function if the protocol outputs the correct value on inputs coming from the subset,the protocol is allowed to output anything on other inputs.For partial functions,a tensor is monochromatic if it doesn't contain both 1-and 0-inputs.Indeed,as long as a protocol reaches a monochromatic tensor, then it can output a value that is right for all inputs on which the function is defined. 2.2 Disjointness Denote the input by (x1,...,xk)where eachxi=xi...xin is an n-bit string.Recall that Disjn in two-party case is defined as,in our current notation,Disjn(x1,x2)=1 iff 3js.t.x=x2j=1.When generalized to k-party case,different requirements can be imposed:We can require 3is.t.x=...= x=1,or only require the sets ,..,xk are not pairwise disjoint.Let's consider the partial function 1 if x1,...,Xk are pairwise disjoint Disjn.k((&,4)=0if3js.t.X=…=X为=1 Theorem 2.2.D(Disjn.k)=R(n/k). Proof.We show the following two properties. 1.There are(k+1)"1-inputs.The input is basically a partition of [n]into k+1 parts,with the i-th part given to player i and the last part unassigned to any player. 2.Any monochromatic tensor without a 0-input contains at most k"I-inputs.Fix a monochromatic tensor.For any element jE [n],there is a player's input xi not containing it.The size the tensor is at most the number ofassignments ofelements in [n]to [k].2. Number in Hand, with a blackboard. 2.1 From rectangle to tensor The counterpart of rectangle in NiH case is tensor. A tensor in X = X1 × …× Xk is a set S = S1 × …× Sk where Si ∈ Xi . The following is a straightforward generalization of the rectangle property. Proposition 2.1. Any c-bit deterministic protocol for a function f in NiH model partitions the set X at most into 2c monochromatic tensors. We sometimes consider partial functions, which are functions with domain not the entire X but only a subset of it. Equivalently, we can imagine that there is a promise that the input comes from a fixed subset of X. For inputs that fall outside the subset, we don’t care. A protocol is correct for this partial function if the protocol outputs the correct value on inputs coming from the subset; the protocol is allowed to output anything on other inputs. For partial functions, a tensor is monochromatic if it doesn’t contain both 1- and 0-inputs. Indeed, as long as a protocol reaches a monochromatic tensor, then it can output a value that is right for all inputs on which the function is defined. 2.2 Disjointness Denote the input by (x1, …, xk) where each xi = xi1…xin is an n-bit string. Recall that Disjn in two-party case is defined as, in our current notation, Disjn(x1,x2) = 1 iff j s.t. x1j = x2j = 1. When generalized to k-party case, different requirements can be imposed: We can require i s.t. x1i = … = xki = 1, or only require the sets x1, …, xk are not pairwise disjoint. Let’s consider the partial function Disjn,k(x1 ,… , xk) = { 1 if x1 ,… , xk are pairwise disjoint 0 if ∃j 𝑠.𝑡. x1j = … = xkj = 1 . Theorem 2.2. D(Disjn,k ) = Ω(n/k). Proof. We show the following two properties. 1. There are (k+1)n 1-inputs. The input is basically a partition of [n] into k+1 parts, with the i-th part given to player i and the last part unassigned to any player. 2. Any monochromatic tensor without a 0-input contains at most kn 1-inputs. Fix a monochromatic tensor. For any element j ∈ [n], there is a player’s input xi not containing it. The size the tensor is at most the number of assignments of elements in [n] to [k]