time in total,the number of transfers is at most T(ny2n.Altogether,the communication is at most S(n)T(n)/2n,as claimed. 2.Query complexity. While we usually talk about O(n2)or O(n)time complexity,sometimes the data is too large and it's not even affordable to read the entire data.(Consider the Internet traffic,or phone record,citation graph,etc.)Fortunately,for some computational problems,we don't need to read the entire input (though the function does depend on all input variables). For a function f:{0,l}n→{0，l},a query algorithm makes queries in the form of“x=?”.A query algorithm computes f if it outputs f(x)correctly for each input x.The algorithm can be deterministic, randomized,or quantum.As previously,we sometimes allow a small error probability for randomized and quantum algorithms(though we won't talk about quantum algorithms in this course).The cost of an algorithm is the maximum number of queries it needs to make,and the query complexity of a function f is the minimum cost of any query algorithm that computes f. Example 2.1:Address functions.The function fhas two parts of input,an n-bit string x and a log(n)-bit string i.The function is defined as f(x,i)=xi,namely treat the second part input as an index of position,on which the value of the first part input is the function value.Note that the function does depend on all n+log(n)input variables.But there is a simple query algorithm reading only log(n)+1 input bits:First read all bits of the second part input,and then read the ith bit of the first part.The query complexity,log(n)+1,is much smaller than n+log(n),the number of variables. Example 2.2:AND-OR Tree.The function is defined by a complete binary tree,with gates at internal nodes being ANDand OR alternatively with levels.For example,the top gate is AND,and the two second-level gates are OR,and the four third-level gates are AND,and so on.The n leafs correspond to the n input variables.If we evaluate along the gates in the tree from bottom leaves upwards,then the top level gate outputs a value,which defines the function value on that input. If we want to compute the function deterministically,then it's not hard to see that it needs to read all n input variables in the worst case.(Can you show it?)However,if we use randomness,then reading a very small fraction of it is enoughtime in total, the number of transfers is at most T(n)/2n. Altogether, the communication is at most S(n)T(n)/2n, as claimed. 2. Query complexity. While we usually talk about O(n2 ) or O(n3 ) time complexity, sometimes the data is too large and it's not even affordable to read the entire data. (Consider the Internet traffic, or phone record, citation graph, etc.) Fortunately, for some computational problems, we don't need to read the entire input (though the function does depend on all input variables). For a function f:{0,1}n→{0,1}, a query algorithm makes queries in the form of “xi = ?”. A query algorithm computes f if it outputs f(x) correctly for each input x. The algorithm can be deterministic, randomized, or quantum. As previously, we sometimes allow a small error probability for randomized and quantum algorithms (though we won’t talk about quantum algorithms in this course). The cost of an algorithm is the maximum number of queries it needs to make, and the query complexity of a function f is the minimum cost of any query algorithm that computes f. Example 2.1: Address functions. The function f has two parts of input, an n-bit string x and a log(n)-bit string i. The function is defined as f(x,i) = xi , namely treat the second part input as an index of position, on which the value of the first part input is the function value. Note that the function does depend on all n+log(n) input variables. But there is a simple query algorithm reading only log(n)+1 input bits: First read all bits of the second part input, and then read the ith bit of the first part. The query complexity, log(n)+1, is much smaller than n+log(n), the number of variables. Example 2.2: AND-OR Tree. The function is defined by a complete binary tree, with gates at internal nodes being AND and OR alternatively with levels. For example, the top gate is AND, and the two second-level gates are OR, and the four third-level gates are AND, and so on. The n leafs correspond to the n input variables. If we evaluate along the gates in the tree from bottom leaves upwards, then the top level gate outputs a value, which defines the function value on that input. If we want to compute the function deterministically, then it’s not hard to see that it needs to read all n input variables in the worst case. (Can you show it?) However, if we use randomness, then reading a very small fraction of it is enough