Abstract In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BHH). BHH is a generalization of the well-known Boolean Hidden Matching problem, which was used by Gavinsky et al. to prove an exponential separation between quantum communication complexity and one-way randomized communication complexity. We are the first to introduce BHH, and to prove a lower bound for it. Abstract The hardness of the BHH problem is inherently oneway: it is easy to solve BHH using logarithmic two-way communication, but it requires √ n communication if Alice is only allowed to send messages to Bob, and not vice-versa. This one-wayness allows us to prove lower bounds, via reductions, for streaming problems and related communication problems whose hardness is also inherently one-way. Abstract By designing reductions from BHH, we prove lower bounds for the streaming complexity of approximating the sorting by reversal distance, of approximately counting the number of cycles in a 2-regular graph, and of other problems. Abstract For example, here is one lower bound that we prove, for a cycle-counting problem: Alice gets a perfect matching EA on a set of n nodes, and Bob gets a perfect matching EB on the same set of nodes. The union EA ∪ EB is a collection of cycles, and the goal is to approximate the number of cycles in this collection. We prove that if Alice is allowed to send o( √ n) bits to Bob (and Bob is not allowed to send anything to Alice), then the number of cycles cannot be approximated to within a factor of 1.999, even using a randomized protocol. We prove that it is not even possible to distinguish the case where all cycles are of length 4, from the case where all cycles are of length 8. This lower bound is "natively" one-way: With 4 rounds of communication, it is easy to distinguish these two cases. Introduction Streaming algorithms are algorithms that read the input from left to right, use a small amount of space, and approximate some function of the input. Their behavior is typically measured by a tradeoff between space consumption and approximation factor. Some classical streaming problems are for example estimating frequency moments, finding approximate quantiles, and other statistics of data-sets (see [26] for more). In recent years, research has increasingly focused on stream-ing algorithms for estimating complex distance metrics between strings, such as earth mover distance [2] , edit distance [4, 5, 3] , and others. These are interesting both because of their relevance in applications, and because they are so challenging: they provide good testing grounds for exploring current techniques and coming up with new ones, both for upper bounds and for lower bounds. Introduction Streaming lower bounds (i.e. lower bounds on the space required) often rely on reductions to communication complexity: we give Alice the first half of the input, give Bob the second half, and require them to return an answer to the problem. A lower bound on communication complexity immediately implies a lower bound on the space usage of a streaming algorithm. In fact, since the input is read left-to-right, it is enough to prove a lower bound on the one-way communication complexity, namely where Alice is only allowed to send messages to Bob, but not vice-versa (and Bob is the player who outputs the answer). However, in many lower bounds the one-wayness is never used: the communication lower bound is proved in the two-way setting, i.e. when Alice and Bob can communicate back and forth. This is a strength, not a weakness: it means that the community is proving stronger lower bounds than those actually necessary. However, considering the fact that for some problems (e.g. edit distance) the known lower bounds are exponentially far from the known upper bounds, this might arouse suspicion that we are missing techniques for proving natively one-way lower bounds. With enough understanding of one-way bounds we might gain the tools to prove stronger streaming lower bounds than those known. (Andoni and Krauthgamer explicitly discuss this point in [4] , and suggest that to get better streaming lower bounds for edit distance, it might be prudent to prove "natively one-way" lower bounds for edit distance.) Indeed, the current paper focuses on problems whose lower bounds are natively one-way, in the sense that the two-way complexity of many of them is exponentially smaller than the one-way complexity. Introduction Many classical problems, such as frequency moments, can be reduced to communication problems such as the Gap-Hamming problem (see e.g. [23, 10, 11] ), and the Set Disjointness problem [9, 1] . For problems of estimating complicated metrics such as those discussed above, lower bound techniques seem to be much more complicated, requiring embedding arguments [3] and direct sum arguments, among others. Naturally, progress on lower bounds has been slow for those problems, and the lower bounds proved are typically logarithmic, not polynomial. Introduction In this paper we show a technique for proving streaming lower bounds that uses one-wayness in an inherent manner, and proving nearly-linear lower bounds on the space usage. (Note that linear space is sufficient for any streaming problem since we can just store the whole input). We prove lower bounds for an approximate cycle-counting problem, for estimating the sorting by reversal distance, and for other problems. Our techniques almost, but not quite, prove lower bounds for the edit distance with block moves problem, which was studied by Cormode and Muthukrishnan [13] . 1 Our lower bounds are proved by a series of reductions to a seemingly "canonical problem" (which we introduce), called Boolean Hidden Hypermatching (BHH); this problem is a variant on the well-known Boolean Hidden Matching problem [18, 19] . The reductions that we show to this problem, while non-trivial, do not require technically-complicated tools. This raises hope that there might be other results that can be proved by similar reductions, creating a new "canonical problem", along with Gap Hamming, Disjointness, etc. The BHH problem seems to capture the hardness of the problems that we study in various natural ways, and it seems like it might capture aspects of hardness of other problems. Introduction We proceed by describing some of the problems discussed in this paper, and the lower bounds we prove for them. The Problems We now describe some of the problems we consider in this paper, in their communication versions. Recall that each one-way communication lower bound immediately implies a streaming lower bound. The Problems The Boolean Hidden Hypermatching problem has a slightly baroque definition, so we show here a simplified definition that captures the spirit of the problem. See Definition 2.5 for the actual definition. The Problems Notice most of these are decision problems with a promise, in the sense that there is a promise on the 1 We mention this since the edit distance with block moves problem, suggested to us by Robert Krauthgamer, was the original motivation for our work. We have not proved a lower bound on it, but we do believe that the techniques in the current paper can eventually prove a lower bound for this problem as well. The Problems inputs of Alice and Bob, which states that one of two cases hold, and the goal is always to decide which of the two cases holds. This kind of problems are particularly suitable when discussing approximation; for example they can ask: given that the value of the instance is either ≤ a or ≥ b, decide between the case where it is ≤ a and the case where it is ≥ b. This kind of hardness implies a hardness of approximation up to a multiplicative value of b/a, but it is conceptually more "fine-grained". The Problems Boolean Hidden Matching (BHM) -Inaccurate Version. In this problem, Alice is given an n-bit string x ∈ {0, 1} n . Bob gets a perfect matching M on n vertices. Thus, the n bits of Alice are matched up in pairs, but the matching is not known to Alice. The promise is that either each matched-up pair of bits is unequal, or each matched-up pair of bits is equal. The goal is to determine which of these two cases holds. The Problems Gavinsky et al [18, 19] proved a lower bound of Ω( √ n) for a variant of this problem called Partial Matching. We extend that result to the Boolean Hidden Matching problem in this paper. The Problems Boolean Hidden HyperMatching (BHH) -Inaccurate Version. This is the same as the BHM problem, but where the matching M is in fact a tuniform hypermatching. In other words, the n bits of Alice are partitioned to n/t disjoint sets of cardinality t each, and the promise is that either each matched-up set of bits XORs to 1, or each matched-up set of bits XORs to 0. The goal is to determine which of these two cases holds. The Problems For this problem, we prove a lower bound of Ω(n 1−1/t ). The proof is similar to that of [19] but we need to generalize various aspects of the proof to deal with hypermatchings and the stronger promise. The Problems Cycle Counting -Gap Version. Alice gets a perfect matching E A on a bipartite graph with n vertices on each side, and Bob gets a prefect matching E B on the same graph. The union E A ∪ E B is a collection of disjoint cycles. They wish to approximate the number of cycles in the union. The goal is to decide between the case that the number of cycles is ≤ a and the case where the number of cycles is ≥ b. The Problems We consider the special case of this problem where b = 2a and where b divides n (e.g. b = n/2, n/3, . . .). We prove a lower bound of Ω (n/2) 1−b/n on the randomized one-way communication complexity. This implies, for example, that when we wish to decide between the case that there are ≤ n/4 cycles and the case there are ≥ n/2 cycles, the communication complexity is Ω( √ n). This lower bound is proved by a reduction to the Boolean Hidden Hypermatching problem. The Problems Deterministic variants of this problem was studied by Raz [27] and by Harvey [22] , but the deterministic case is very different from the randomized case. In particular, it is easy to see that a simple hashingbased protocol can estimate to excellent accuracy the number of cycles of length 2, yielding a protocol that distinguishes the case of ≤ 0.1n cycles from the case of ≥ 0.9n cycles with O(1) communication and probability of success 0.999. Such a protocol probably does not exist in the deterministic setting. The Problems Sorting by Reversals. The input is a signed permutation x of {1, . . . , n}: this is a permutation where each element is also assigned a sign of plus or minus. Alice gets the first half of this permutation (i.e. the first n/2 elements), and Bob gets the second half. They wish to estimate the reversal distance, namely the smallest number of reversals required to transform x to the positive identity permutation, (+1, +2, . . . , +n). A reversal is the operation of choosing a block of the permutation x, reversing the order of the elements and flipping the signs. The Problems There is a known (and rather complicated) polynomial-time algorithm that given x computes exactly the reversal distance of x [20] . There is even a linear-time algorithm that achieves this [6] . However, here we are interested in the communication complexity (or streaming complexity) of approximating the reversal distance. The Problems For this problem, we prove a lower bound of Ω((n/8) 1−1/t ) on the randomized one-way communication complexity of getting a (1 + 1/(4t − 2) − )-multiplicative approximation of the reversal distance (for any > 0). For example, to get a 1.166-approximation, Ω( √ n) communication is required. To get a 1.0001-approximation, Ω(n 0.999 ) communication is required. The Problems We also prove lower bounds for sorting by block interchanges and a few other problems. Furthermore, we discuss the problems of sorting by transpositions and of edit distance with block moves, but we do not prove lower bounds for them. The Problems One observation to note is that BHH is qualitatively different than sorting by reversals or cycle counting, in that it is highly non-symmetric: the role of Alice is entirely different than the role of Bob. Another way to express this idea is that for the BHH problem, if Bob is allowed to send one message to Alice instead of Alice sending a message to Bob, the BHH problem becomes easy (t log n bits of communication suffice). This does not hold for the other problems: in the other problems, if Bob is allowed to send one message to Alice, the lower bounds stay the same. The Problems The structure of our reductions is depicted in Figure 1. In Section 5 we outline some ideas behind this work and pose some conjectures that might motivate future work. The reader might wish to skim it before moving on. Main Results In this section we prove that Sorting-by-Reversal and Sorting-by-Block-Interchanges in the streaming model requires space Ω((n/8) 1−1/t ) to achieve approximation factor 1 + 1/(4t − 2). That is, in order to achieve 1 + approximate, a lower bound of Ω((n/8) List of Applications The main problem we investigate is the Sorting-by-Reversal problem in the streaming model. List of Applications We also talk about Sorting-by-Block-Interchanges and Sortingby-Transpositions problem. However, we do not have a formalized lower bound for the Sorting-byTranspositions problem. List of Applications Definition 2.1. (Sorting-by-Reversal) Given a data stream of a permutation S on {1, . . . , n} where each coordinate of S is also assigned with a sign of plus or minus. We define a reversal r(i, j) on x transforming x = (x 1 , . . . , x n ) to List of Applications In the Sorting-by-Reversal problem we want to return the minimum number of reversals sbr(S) in order to sort S (i.e. transform S into (1, 2, . . . , n)) within 1+ multiplicative factor by scanning the data stream in one pass. Definition 2.2. (Sorting-by-Block-Interchanges) Given a string of permutation x, we define a blockinterchange r(i, j, k, l) where Definition 2.2. (Sorting-by-Block-Interchanges) The goal of Sorting-by-Block-Interchanges is to approximate the minimum number of blockinterchanges to sort x in increasing order (i.e. 1, 2, . . . , n) by scanning one pass on the input. Definition 2.2. (Sorting-by-Block-Interchanges) The goal of Sorting-by-Transpositions is to approximate the minimum number of transpositions to sort x in increasing order by scanning one pass on the input. Definition 2.2. (Sorting-by-Block-Interchanges) A polynomial approximation algorithm in the nonstreaming model was proposed in [12] . We do not have a lower bound for the SBT problem in this paper but we believe it is closely related to our result (see Conjecture 5.3). Cycle Counting and Boolean Hidden Hypermatching Problem In this subsection we define the Gap Cyc-Counting (abbr. GCC) problem used in the reduction to get the lower bound for above listed problems. The GCC problem is a communication complexity problem with parameters a and b as following. Cycle Counting and Boolean Hidden Hypermatching Problem to be a bipartite graph with U and V being the vertices on two sides respectively where |U | = |V | = n. Alice receives E A , a perfect matching in G; and Bob receives E B , another perfect matching in G. In the Gap Cycle-Counting problem it is promised that the number of cycles in G is either ≤ a or ≥ b. They want to Cycle Counting and Boolean Hidden Hypermatching Problem • return 0, when the number of cycles in G ≤ a; Cycle Counting and Boolean Hidden Hypermatching Problem • return 1, when the number of cycles in G ≥ b. Cycle Counting and Boolean Hidden Hypermatching Problem Note that this problem could also be defined as deciding the number of cycles is either ≤ a or ≥ b in the product uv of two permutations u, v ∈ S n where S n is the symmetric group of order n. Cycle Counting and Boolean Hidden Hypermatching Problem We reduce the GCC problem from the Boolean Hidden Hypermatching problem, which is a variant of the Partial Matching problem proposed in [19] , which is actually a generalization of the Boolean Hidden Matching [8] problem. n where n = 2kt for some integer k, and Bob gets a perfect hypermatching M on n vertices where each edge has t vertices and a boolean vector w of length n/t. Let M x denote the length-n/t boolean vector Cycle Counting and Boolean Hidden Hypermatching Problem The problem is to return 1 when M x ⊕ w = 1 n/t , and 0 when M x ⊕ w = 0 n/t . Cycle Counting and Boolean Hidden Hypermatching Problem The main theorem of this paper is the following lower bound for BHH t n . Cycle Counting and Boolean Hidden Hypermatching Problem Theorem 2.1. The randomized one-way communication complexity of BHH t n when n = 2kt for some integer Cycle Counting and Boolean Hidden Hypermatching Problem This theorem is proved in Section 3. This lower bound is the best possible up to a log factor because of a birthday paradox upper bound: Alice can just send O(n 1−1/t ) random indices from x and with good probability Bob will get all of the values of one of the hyperedges. For deterministic and one-sided error protocols we can get linear lower bounds; we omit their proofs here. Cycle Counting and Boolean Hidden Hypermatching Problem Lemma 2.1. If there is a randomized one-way protocol for GCC 2n (n/t, 2n/t), then there is a randomized oneway protocol for BHH t n problem on n vertices using the same communication and error probability. Cycle Counting and Boolean Hidden Hypermatching Problem Proof. Consider an instance of the BHH t n problem: Alice gets a boolean vector x of length n, and Bob gets a hypermatching M of n/t edges where each edge is of size t, as well as a boolean vector w of length n/t. Cycle Counting and Boolean Hidden Hypermatching Problem We now construct an instance of the GCC problem. It is a bipartite graph (U ∪ V, E A ∪ E B ), where U = {u 1 , . . . , u 2n } and V = {v 1 , . . . , v 2n }. Here, E A and E B are Alice's and Bob's input respectively which are perfect matchings in the bipartite graph. For each i ∈ [n], we place the following edges in E A : Cycle Counting and Boolean Hidden Hypermatching Problem • If x i = 0 then place (u 2i−1 , v 2i−1 ) ∈ E A and (u 2i , v 2i ) ∈ E A ; we call this a parallel gadget; Cycle Counting and Boolean Hidden Hypermatching Problem • If x i = 1 then place (u 2i−1 , v 2i ) ∈ E A and (u 2i , v 2i−1 ) ∈ E A ; we call this a cross gadget. Cycle Counting and Boolean Hidden Hypermatching Problem That is, a "parallel gadget" for x i = 0, or a "cross gadget" for x i = 1. Then for each hyperedge (i 1 , i 2 , . . . , i t ) ∈ M , Cycle Counting and Boolean Hidden Hypermatching Problem • For k = t, if w i = 0, we just let Cycle Counting and Boolean Hidden Hypermatching Problem (The latter case means that we add an extra "cross gadget" if Cycle Counting and Boolean Hidden Hypermatching Problem It is easy to see that if |{k|x i k = 1}| = p, then we go through p+w i cross gadgets when traversing from u 2i1−1 along the cycle. Thus, if p + w i is odd then there will be one cycle of length 4t, otherwise there will be two cycles of length 2t. So if the correct result for BHH t n is 1, we know that for any hyperedge i, p + w i is always odd. It means that the number of cross gadgets is odd, so each hyperedge will form two cycles of length 2t, which means the number of cycles is 2n/t. If the result is 0, by a similar argument the number of cycles will be n/t. Cycle Counting and Boolean Hidden Hypermatching Problem A randomized protocol for GCC(n/t, 2n/t) on 4n vertices will, with probability 1 − , return 0 if the number of cycles is ≤ n/t and will return 1 if the number of cycles is ≥ 2n/t. So for an input from BHH t n we can turn it into two matchings in the above way. After that we can invoke the protocol for GCC 2n (n/t, 2n/t) vertices to get a protocol for BHH t n . Cycle Counting and Boolean Hidden Hypermatching Problem By using Lemma 2.1 with Theorem 2.1, we obtain the following lower bound for Gap Cycle-Counting problem. Cycle Counting and Boolean Hidden Hypermatching Problem Corollary 2.1. The randomized one-way communication complexity with error probability 1/100 of GCC n (n/2t, n/t) for any integer t|n is Ω((n/2) 1−1/t ). Cycle Counting and Boolean Hidden Hypermatching Problem Note that this reduction actually suffers from a loss in the hardness of the GCC problem. The GCC problem is hard no matter if the one-way communication is from Alice to Bob or from Bob to Alice. However, the BHH problem is easy if Bob speaks to Alive, since Bob could just send one edge using t log n. Hardness of Sorting-by-Reversal and Sorting-by-Block-Interchange We already see the hardness of the Gap Cycle-Counting (abbr. GCC) problem, and we are going to show that the Sorting-by-Reversal (abbr. SBR) and Sortingby-Block-Interchanges (abbr. SBI) problems in the streaming model are also hard. We do this by relating the number of cycles in the breakpoint graph of the permutation to the number of cycles in the input of GCC. Hardness of Sorting-by-Reversal and 2 , the breakpoint graph G of S is constructed by the following algorithm. Hardness of Sorting-by-Reversal and • From S we construct another integer array T of length 2n + 2. Hardness of Sorting-by-Reversal and • Hardness of Sorting-by-Reversal and , where E is constructed as following. Hardness of Sorting-by-Reversal and ) ∈ E and we call these edges black edges. Hardness of Sorting-by-Reversal and ) ∈ E and we call these gray edges. Hardness of Sorting-by-Reversal and In short, we expand an integer in S to two according to its sign, after that we insert 0 at the front and 2n + 1 to the rear. After that, we connect every other pairs and every pair that the value only differs by one but not expanded from the same integer. The breakpoint is a standard and useful tool to get SBR and SBI distance from the number of cycles. For further understanding on the breakpoint graph (sometimes also called as cycle graph), the reader might want to read [20, 17] . Lemma 2.2. Let E A and E B to be two perfect matchings on bipartite graph of size 2n (n vertices on each side). And let C to be the number of cycles in E A ∪ E B . We can transform E A to an integer array S 1 and E B to another integer array S 2 , such that S = S 1 + S 2 is a signed permutation of [4n] which has 2C + 1 cycles in its breakpoint graph. Moreover, let S 1 and S 2 satisfy Hardness of Sorting-by-Reversal and | is an unsigned permutation of [4n] which also has 2C + 1 cycles in its breakpoint graph. Hardness of Sorting-by-Reversal and Before proving the lemma, we first show how to get the lower bound of SBI by using this lemma. Theorem 2.2. The lower bound of the space in the streaming model for Sorting-by-BlockInterchange when we want to approximate the correct distance up to multiplicative factor 1 + 1/(4t − 2) − for any small constant is Ω((n/8) 1−1/t ). Hardness of Sorting-by-Reversal and Proof. Assuming the space used in the streaming algorithm for computing the Sorting-by-BlockInterchange distance here is S, we can cut the stream in the middle and split it into two sets of numbers of size n/2. Thus by the standard reduction we can turn the streaming algorithm into a one-way communication complexity protocol, where Alice holds the first part of the stream and the Bob holds the second part of the stream. After Alice simulates her input with the streaming algorithm, she can send S bits to Bob which is the memory sketch of the algorithm, and Bob can resume the algorithm after that to get the correct answer. Thus, if we can give a lower bound for this one-way communication complexity version of the problem, there will be a lower bound for S. Say in the GCC n/4 (n/4t, n/8t) problem Alice receives a matching E A in a bipartite graph of n/2 vertices (n/4 vertices on each side) and Bob receives another matching E B and they want to decide the number of cycles in E A ∪ E B is either ≥ n/4t or ≤ n/8t. We can transform E A and E B to S 1 and S 2 by using Lemma 2.2. Let C to be the number of cycles in E A ∪ E B , then we know that the number of cycles in the breakpoint graph of S 1 +S 2 is 2C +1. We also know that the SBI distance of S = S 1 + S 2 satisfies sbi(S ) = (n − 2C)/2 because of the following lemma from [12] . Assuming we have a streaming algorithm for approximating the SBI distance using space S, by the above discussion we can turn it into a one-way communication complexity protocol for approximating the SBI distance of S by using S bits where Alice holds S 1 and Bob holds S 2 . Hardness of Sorting-by-Reversal and However, if this protocol can approximate up to 1 + 1/(4t − 2) − for some integer t ≥ 2, then we can distinguish SBI distance n − n/2t from distance n − n/4t since (1 + 1/(4t − 2) − ) · (n − n/2t) < n − n/4t. Thus it means that a protocol that approximates SBI distance within 1 + 1/(4t − 2) − will be able to distinguish the C ≤ n/4t case and the C ≥ n/2t case by simply comparing (n − 2sbi(S ))/2 with n/2t. By using Corollary 2.1 we have a lower bound of Ω((n/8) 1−1/t ) for approximating SBI distance on an array of length n with factor 1 + 1/(4t − 2) − for any constant > 0. Hardness of Sorting-by-Reversal and We are expecting to repeat the same proof for SBR. But this does not work straight forward because we do not have things like Lemma 2.3 for SBR. We can only have the following conditional lemma for SBR from [20] . Hardness of Sorting-by-Reversal and < . . . < i k . Otherwise, we call the cycle oriented. It could be observed that in the breakpoint graph a cycle is oriented iff it has length 2, or there is a gray edge (i, j) in the cycle that both i and j are left ends (or both right ends) of black edges. Hardness of Sorting-by-Reversal and Fortunately, we can prove that the breakpoint graph constructed in our reduction only has oriented cycles. Lemma 2.5. All cycles in the breakpoint graph of the signed permutation constructed in Lemma 2.2 are oriented. Hardness of Sorting-by-Reversal and So by combining this lemma with Lemma 2.4 we can have the lower bound for SBR by repeating the same proof in Theorem 2.2 with SBR. Theorem 2.3. The lower bound of the space in the streaming model for Sorting-by-Reversal when we want to approximate the correct answer up to multiplicative factor 1 + 1/(4t − 2) − for any small constant is Ω((n/8) 1−1/t ), where n is the number of integers in the stream. Hardness of Sorting-by-Reversal and Proof. Using S instead of S , and using Lemma 2.5 and Lemma 2.4 instead of Lemma 2.3, it is easy to see we can repeat the same proof for 2.2 to get the same lower bound. Proof of Lemma 2.2 and Lemma 2.5 There are two lemmas still left unproved, we prove them here. Lemma 2.6. (Lemma 2.2 Restated) Let E A and E B to be two perfect matchings on bipartite graph of size 2n (n vertices on each side). And let C to be the number of cycles in E A ∪ E B . We can transform E A to an integer array S 1 and E B to another integer array S 2 , such that S = S 1 + S 2 is a signed permutation of Proof. Starting with E A and E B as perfect matchings, we construct S as following. Lemma 2.6. (Lemma 2.2 Restated) • For each edge (u i , v j ) ∈ E A , S 1 [2j] = 2j and Lemma 2.6. (Lemma 2.2 Restated) Since E A is a permutation, all the indices in {1, . . . , 2n} are assigned. Lemma 2.6. (Lemma 2.2 Restated) • For each edge ( Lemma 2.6. (Lemma 2.2 Restated) The breakpoint graph G = (P, E) of S could be constructed according to Definition 2.6, which is also illustrated in Figure 2 . Lemma 2.6. (Lemma 2.2 Restated) We are going to show the number of cycles in the breakpoint graph G is 2C + 1, where C is the number of cycles E A ∪ E B . Lemma 2.6. (Lemma 2.2 Restated) Let Lemma 2.6. (Lemma 2.2 Restated) be a cycle of length m in G. And we know that (u i k , v j k ) ∈ E A and (u i k+1 , v j k ) ∈ E B . We are going to show there are two corresponding cycles in G, say 4n+4i Lemma 2.6. (Lemma 2.2 Restated) · · · → 4n + 4i 1 + 1 4n + 4i 1 where → denotes black edge and denotes gray edge. Note that the direction here are just for the convenience of presentation, the cycles are actually undirected. This could be observed by the following facts. Lemma 2.6. (Lemma 2.2 Restated) • (4j 1 −4, 4n+4i 1 −1) and (4n+4i 1 , 4j 1 −1) are black edges. This is because (u i1 , v j1 ) ∈ E A , so either 2j 1 − 2, −(2n + 2i 1 ), 2j 1 are consecutive integers in S or j 1 = 1 and −(2n + 2i 1 ), 2 are consecutive integers in S. Lemma 2.6. (Lemma 2.2 Restated) • (4j 1 − 1, 4j 1 − 2) and (4j 1 − 4, 4j 1 − 3) are gray edges. Lemma 2.6. (Lemma 2.2 Restated) • (4j 1 − 3, 4n + 4i 2 + 1) and (4j 1 − 2, 4n + 4i 1 − 4) are black edges. This is because (u i2 , v j1 ) ∈ E B , so either 2n + 2i 2 − 1, −(2j 1 − 1), 2n + 2i 2 + 1 are consecutive integers in S or i 2 = n and 4n, −(2j 1 − 1) are the last integers in S. Lemma 2.6. (Lemma 2.2 Restated) • (4n+4i 2 −2, 4n+4i 1 −3) and (4n+4i 2 +1, 4n+4i 2 ) are gray edges. Lemma 2.6. (Lemma 2.2 Restated) All these cycles in E A ∪ E B will use 8n edges in all. There are only two edges left. But there is another cycle which is 4n + 1 → 4n + 2 4n + 1 of length 2 which are just formed by the edges left. So the number of cycles in G is 2C + 1, where C is the number of cycles in E A ∪ E B . (And, the reader could also observe that all the cycles in G has twice the length as the cycles in Lemma 2.6. (Lemma 2.2 Restated) For the cycles in the breakpoint graph of S the proof is similar. We omit the details and refer the reader to (d) in Figure 2 . Proof. According to the construction all the gray edges except (4n + 2, 4n + 1) are of the kind (4j 1 − 1, 4j 1 − 2) ,(4j 1 − 4, 4j 1 − 3), (4n + 4i 2 − 2, 4n + 4i 1 − 3) and (4n + 4i 2 + 1, 4n + 4i 2 ). And since 4j 1 − 1, 4j 1 − 2, 4n + 2i 1 + 1, 4n + 4i 1 are all right ends of black edges, and 4n + 4i 2 − 2, 4n + 4i 1 − 3, 4j 1 − 4, 4j 1 − 3 are all left ends of black edges, we have that all these cycles are oriented. We refer the reader to (c) in Figure 2 . Lemma 2.6. (Lemma 2.2 Restated) And the cycle 4n + 1 → 4n + 2 4n + 1 is just a length 2 cycle, which is also oriented. Thus it means the SBR distance is 4n + 1 − (2C + 1) = 4n − 2C. Lower bound of BHH In this section we prove a lower bound on the BHH t n problem. Together with the reductions in the previous sections, it gives the main result of the paper. Notations A t-dimensional hypermatching M is a set of vertex disjoint edges, and each edge is a set of t vertices. In this paper for a given boolean vector x we are in particular interested in the XOR value of the edges on this vector. That is, if the edges of M are (i 1,1 , . . . , i 1,t ), · · · , (i n/t,1 , . . . , i n/t,t ), we are interested in values 1≤k≤t x i 1,k , · · · , 1≤k≤t x i n/t,k . We use M x to denote this vector. Notations Another way of representing the hypermatching M is a n/t × n matrix. Each row of the matrix has t 1's and n − t 0's denote the corresponding position of an edge. The advantage of this representation is that when computing the XOR values of all the edges on vector x in the matching, it is equivalent to performing the matrixvector multiplication M x. Thus we abuse notation and use M both for the hypermatching and the matrix. Note that in the matrix multiplication here, all computations are modulo 2. Notations In the t = 2 case M is a perfect matching on n vertices. This was the case discussed in [19] . Lower bound of BHH We now prove a lower bound for the BHH t n problem (see Definition 2.5). The proof here extends the proof in [19] to t-hypermatching case when n = 2kt. We are using the same framework and notations as in [19] . Lower bound of BHH The main difference here is we need to talk about perfect hypermatching instead of partial matching. In order to show a lower bound for the perfect matching, we need to think of the case that n = 2kt and talk about single parity sets (for definition see below). For extending to hypermatching, we need to recompute all the parameters used in [19] . The reader may want to read [19] to get a better understanding of the proof. Lower bound of BHH The basic idea of the proof is the following. First, we apply Yao's minimax principle, after that we can talk about deterministic protocols under distributional inputs. Alice's message is short, so after Bob looks at her message, there are typically still many possible inputs of Alice that he cannot tell apart. In other words, let l to be the length of the message sent from Alice to Bob, then the number of inputs for which Alice sends a specific message is typically 2 n−l , which is a large number. Let X be a r.v. uniformly distributed in a set of size ≥ 2 n−l that corresponds to one specific message from Alice to Bob. We are going to show that for most of the hypermatchings M , if 2 n−l is large, the distribution of M X is nearly the same as M X, which means Bob cannot distinguish these two cases. So l must be large to make such kind of sets small. Note that unlike [19] here M X and M X are close to each other, but neither of them is close to uniform distribution. n a single parity set iff ∃c ∈ {0, 1}, ∀x ∈ A, |x| ≡ c (mod 2), i.e., all the elements in A have the same weight parity. Theorem 3.1. Let n = 2pt for some integer p, and x be uniformly distributed over a single parity set A ⊆ {0, 1} n of size |A| ≥ 2 n−l for some l ≥ 1, and let M be uniformly distributed over the set M n,t of all thypermatchings on n vertices. There exists a universal constant γ > 0 (independent of n, l, t, ), such that for all Lower bound of BHH where p M and q M are the distributions over {0, 1} Lower bound of BHH and respectively. It is important n needs to be an even multiple of t, otherwise there is a simple constant upper bound by sending the parity of x to Bob. We leave the proof of this theorem in Section 4, we will show in detail how to get the lower bound of BHH t n from it. t with error probability ≤ 1/100 has at least Ω(n 1−1/t ) bits. respectively. Proof. Think of a protocol with error ≤ . By Yao's principle, there must be a deterministic protocol which has distributional error ≤ under the following chosen "hard distribution". We choose Alice's input X and Bob's input M independently and uniformly at random; then we choose w = M x with probability 1/2 and w = M x with probability 1/2. Let Π be the transcript of the protocol. In our case, Π is just one message, of length ≤ l, sent from Alice to Bob. The transcript can be thought of splitting Alice's input into disjoint single parity sets A 1 , A 2 , . . . , A 2 l+1 , where each set contains all the inputs for which she sends the same message and single parity. Consider all such sets bigger than 2 n /(100 · 2 l+1 ). It is trivial to see that least 99% of the universe is covered by such sets. Therefore, with probability 0.99, the message sent from Alice to Bob is from a set of size ≥ 2 n /(100 · 2 l+1 ). Let such a set to be A, and let X be a random variable uniformly distributed on A, and let Z = M X for some M which is a prefect t-hypermatching on n vertices. Let Z 0 = Z and respectively. 1−1/t and we know A is single parity. Thus we can use Theorem 3.1 to get EM [∆(Z 0 , Z 1 )] < 1/100. By Markov bound, for at least 1 − 1/10 fraction of all M , ∆(Z 0 , Z 1 ) ≤ 1/10. For all the M in that case, by looking at w Bob needs to decide which distribution w is from. That is, Bob needs to distinguish two distributions Z 0 and Z 1 . Since it is well known that the best protocol to distinguish 1/10-close (i.e. ∆(Z 0 , Z 1 ) ≤ 1/10) distributions errs with probability ≥ 1/2 − 1/40 (see also [19, Eq 1.1]) . So we know that the total error will be ≥ 9/10·(1/2−1/40)·99% > 1/100, which contradicts the assumption. Thus l > Ω(n 1−1/t ) and we are done. Proof for Theorem 3.1 In this section we prove Theorem 3.1. Preliminaries on Fourier Analysis Here we need the standard definitions [15] of discrete Fourier analysis. Let f : {0, 1} n → R be a function on the boolean cube. We define the inner product on boolean functions by Preliminaries on Fourier Analysis This also defines the 2 -norm Preliminaries on Fourier Analysis The Fourier transform of f is a functionf : Preliminaries on Fourier Analysis where χ S : {0, 1} n → R is the character function χ S (y) = i∈S (2y i − 1). For the sake of convenience, we also use s to denote the characteristic boolean vector of s, e.g. χ s can also be defined by χ s (y) = (−1) Preliminaries on Fourier Analysis y·s . We will need Pareseval's identity. Preliminaries on Fourier Analysis And we need the following lemma, which is a direct consequence of the Bonami-Gross-Beckner inequality, or hypercontractivity inequality from KKL [24] . Let |x| denote the Hamming weight of x, i.e., number of 1's in the boolean vector x. Preliminaries on Fourier Analysis Thus, Preliminaries on Fourier Analysis It could be easily observed that for a fixed k, Preliminaries on Fourier Analysis we have the following claim to be proved later. Claim 4.2. Let x ∈ {0, 1} n such that |x| = kt. We define Claim 4.2. Let x ∈ {0, 1} where M is uniformly over all t-hypermatchings on n vertices. Thus g(k) = g(n/t − k) and Claim 4.2. Let x ∈ {0, 1} Since we know that Claim 4.2. Let x ∈ {0, 1} Because A is a single parity set, we havef (v) Claim 4.2. Let x ∈ {0, 1} 2 by Claim 4.1. And since g(k) = g(n/t − k) and 2t|n from the statement of the theorem, we have, Claim 4.2. Let x ∈ {0, 1} We are going to bound this value by two parts. Part I (1 ≤ kt < 4l). For a fixed k, let δ = kt/4l, we have that Claim 4.2. Let x ∈ {0, 1} where the last inequality holds because k ≥ 1, t ≥ 2 and by choosing γ to be a sufficiently small constant (e.g. 1/1024, independent of k, t). Claim 4.2. Let x ∈ {0, 1} Thus for a fixed k we have Claim 4.2. Let x ∈ {0, 1} Summing up, for < 1/2, we have Claim 4.2. Let x ∈ {0, 1} Part II (4l ≤ kt ≤ n/2). We know that Claim 4.2. Let x ∈ {0, 1} when k ≤ n/2t. Since by Parseval (Lemma 4.1) we have Claim 4.2. Let x ∈ {0, 1} |A| 2 n and we know that Claim 4.2. Let x ∈ {0, 1} As we know Claim 4.2. Let x ∈ {0, 1} where the last step is because t ≥ 2, l ≥ 1 and γ to be a sufficiently small constant (e.g. 1/1024). By summing up the two parts we conclude that Claim 4.2. Let x ∈ {0, 1} Thus, Claim 4.2. Let x ∈ {0, 1} At last we prove Claim 4.2 left in the proof. Claim 4.2. Let x ∈ {0, 1} By dividing the number of all possible matchings n!/((t!) n/t (n/t)!(n − n)!) we have Claim 4.2. Let x ∈ {0, 1} which is called g(k) as a function of k. Ideas Behind this Work and Suggestions for Further Work The approach taken in this paper does not match the authors' original plan. In this section we outline the original thoughts and plans. For future research it might be interesting to use some ideas from these original plans, or even to try to follow them more closely than we did. This might make the results simpler, more elegant, or quantitatively stronger. The original motivation of this work has been to prove a n 1− lower bound on the communication complexity of edit distance with block moves (viz. Conjecture 5.3). Edit distance with block moves is a metric where the distance between two strings x, y is the minimum number of operations required to transform x to y by single-character edit operations (i.e. insertion, deletion and modification of a character) and by block moves (i.e. cutting out an entire block and inserting it elsewhere). Alice gets x, Bob gets y, and they want to approximate the distance between x and y. For this problem, there is a protocol with communication O(1) and approximation factor O(log n log * n), see [13] , which works by an embedding into 1 . In the case that each character appears exactly once in x and exactly once in y, i.e. each string is a permutation, this problem can be called "Ulam distance with block moves", and it is easy to obtain an protocol with communication O(1) and which achieves 2 + approximation, by a simple embedding into 1 , as in [14] . We believe that approximating these problems better than some particular constant factor c > 1 should take at least √ n communication. (1.5 and 2 are both good guesses for the value of c.) We also believe that the closer the approximation factor is to 1, the closer the communication must be to n. Thus, we conjecture for example that for a 1.001-approximation, the communication must be n 0.99 . Such lower bounds would in particular imply strong lower bounds on the space complexity of approximating edit distance with block moves in the streaming model, a well-studied problem. Ideas Behind this Work and Suggestions for Further Work The problem of Ulam distance with block moves is equivalent to a well-known problem in computational biology called Sorting-by-Transpositions (SBT) [7, 21, 16 ]. This problem is neither known to be NPhard nor known to lie in P. Therefore, we decided to start by considering a related problem, Sorting-byReversal (SBR), which is known to lie in P. For this problem, Hannenhalli and Pevzner [20, 25] proved a combinatorial characterization of the distance. This combinatorial characterization heavily relies on the socalled breakpoint graph (see Definition 2.6) which is a 2-regular graph. The distance is "almost" uniquely determined by the number of cycles in this graph. (We say "almost" because the number of "hurdles" and "fortresses" also needs to be taken into account, see [20, 25] for more details.) Furthermore, when we are trying to compute the edit distance between two signed permutations x and y using the HannenhalliPevzner characterization, the breakpoint graph is a union of two matchings, one of which is determined by x and the other is determined by y. We see then that the communication complexity of sorting by reversals is tightly related to the communication complexity of cycle-counting, at least at the conceptual level. This led us to study the communication complexity of the cycle counting problem. Ideas Behind this Work and Suggestions for Further Work For the cycle counting problem, we had originally made the following conjecture: Ideas Behind this Work and Suggestions for Further Work Conjecture 5.1. For the cycle-counting problem, it takes Ω( √ n) communication to distinguish the case where all cycles are of length 4 from the case that there is just one cycle of length 2n. In general, it takes Ω(n 1−1/ ) communication to distinguish the case where all cycles are of length 2 from the case that there is just one cycle of length 2n. Ideas Behind this Work and Suggestions for Further Work We tried to prove this conjecture directly, but failed. Instead, we found that cycle counting reduces to BHH by a rather straightforward reduction, and decided to work on a lower bound for BHH. This reduction together with the lower bound for BHH that we prove, gives Corollary 2.1, which is a weaker result than Conjecture 5.1. For example, Corollary 2.1 tells us that it takes Ω( √ n) communication to distinguish the case that all cycles are of length 4 from the case that all cycles are of length 8, while Conjecture 5.1 tells us that it takes Ω( √ n) communication to distinguish the case that all cycles are of length 4 from the case that there is just one cycle, of length 2n. Ideas Behind this Work and Suggestions for Further Work Back to SBR: First let us ignore the issue of hurdles and
{'paper_id': '5966455', 'title': 'The streaming complexity of cycle counting, sorting by reversals, and other problems', 's2_url': 'https://api.semanticscholar.org/CorpusID:5966455', 'source': 'S2ORC'}