Then,there shoud beat lest(monochromatie teno Therefore.the k theorem follows from the previous proposition. 2.3 Computing frequency moments in data stream Suppose that there is a stream of data x=(x1,...,Xm)E [n]m.We hope to compute some statistical value of the data using a small amount,ideally O(logn logm)bits,of space.The requirement for the algorithms is that we only see the data passing once in front of us.So we can processx in whatever way we like,but then it's gone and never comes back,and we see x2 and process x2,and so on.After formally initialized in a paper [AMS99],the model has been rapidly developed in the last decade or so. To see why sometimes techniquescan be used to achieve low space complexity,let's consider some interesting puzzles first. Example.Suppose m=n-1,and all xi's are different.Then there is exactly one number in [n]that is missing in the data.They want to find out the missing number.What's the lowest space your algorithm can achieve? Example.What if m=n-2 and they want to find the two missing numbers? From the above examples,you can see that algorithms can be crafty,which also raises the issue of proving lower bounds.Communication complexity is one powerful tool to prove lower bounds for space complexity of streaming algorithms.Here we illustrate the main idea using one classic example. In the data x=(x,..,Xm)E [n]m,suppose the number j appears ri times.Define the d-th frequency moment ofx to be fa(x)=n+...+rd.In particular,fo(x)is the number of distinct elements in x, and fi(x)=m.For d>2,fa(x)gives useful statistical information about the string. Theorem2.3.Ford≥3，D(fa)=2(n1-2/a). Proof.The idea is,as always,design a protocol to simulate an algorithm.Suppose that there is an algorithm A computing fa using only c bits of space.Let k=(n+1)1/d.We want to solve the Disjnk problem on input(y,..,y).Note that eachy;is a subset of[n].Player I gives the elements in y to A as a stream of data items and runs A.When A finishes reading these elements,Player 1 pass her space to Player 2 who takes over to continue to run A upon seeing elements in y2,and so on.Since A always uses c bits of space,the communication is at most(k-1)c bits.Since the itemsy;come in aThen, there should be at least (k+1)n kn = (1 + 1 𝑘 ) 𝑛 ≈ 𝑒 𝑛/𝑘 monochromatic tensors. Therefore, the theorem follows from the previous proposition. □ 2.3 Computing frequency moments in data stream Suppose that there is a stream of data x = (x1 , …, xm) ∈ [n]m. We hope to compute some statistical value of the data using a small amount, ideally O(log𝑛 + log𝑚) bits, of space. The requirement for the algorithms is that we only see the data passing once in front of us. So we can process x1 in whatever way we like, but then it’s gone and never comes back, and we see x2 and process x2, and so on. After formally initialized in a paper [AMS99], the model has been rapidly developed in the last decade or so. To see why sometimes techniques can be used to achieve low space complexity, let’s consider some interesting puzzles first. Example. Suppose m = n-1, and all xi’s are different. Then there is exactly one number in [n] that is missing in the data. They want to find out the missing number. What’s the lowest space your algorithm can achieve? Example. What if m = n-2 and they want to find the two missing numbers? From the above examples, you can see that algorithms can be crafty, which also raises the issue of proving lower bounds. Communication complexity is one powerful tool to prove lower bounds for space complexity of streaming algorithms. Here we illustrate the main idea using one classic example. In the data x = (x1, …, xm) ∈ [n]m, suppose the number j appears rj times. Define the d-th frequency moment of x to be 𝑓𝑑 (𝑥) = 𝑟1 𝑑 + ⋯ + 𝑟𝑛 𝑑. In particular, f 0(x) is the number of distinct elements in x, and f1(x) = m. For d ≥ 2, fd(x) gives useful statistical information about the string. Theorem 2.3. For 𝑑 ≥ 3, 𝐷(𝑓𝑑 ) = 𝛺(𝑛 1−2/𝑑). Proof. The idea is, as always, design a protocol to simulate an algorithm. Suppose that there is an algorithm A computing f d using only c bits of space. Let k = (n + 1) 1/d. We want to solve the Disjn,k problem on input (y1, …, yk). Note that each yi is a subset of [n]. Player 1 gives the elements in y1 to A as a stream of data items and runs A. When A finishes reading these elements, Player 1 pass her space to Player 2 who takes over to continue to run A upon seeing elements in y2, and so on. Since A always uses c bits of space, the communication is at most (k-1)c bits. Since the items yi come in a