<p>I would like to ask everyone not to upvote this, as this is not an answer, but an extended comment, in which I would like to argue why this question did not receive any answers. My main point is, that a communication complexity lower bound won't work. By this, I mean that no matter how we cut the input into two parts and give it to two players, A and B, A can transfer a single bit to B from which he can compute the parity of the permutation. (This follows simply by considering inversions.)</p>

<p>Proofs that use another bound are hard.
See this comment here by Noam Nisan (for the non-deterministic version): <a href="https://cstheory.stackexchange.com/questions/20468/bounds-on-the-size-of-the-smallest-nfa-for-l-k-distinct#comment57460_20468">Bounds on the size of the smallest NFA for L_k-distinct</a>,</p>

<p>this related question by myself answered by Hermann Gruber which shows that the communication complexity lower bound can be very far from the truth (again in the non-deterministic version)
<a href="https://cstheory.stackexchange.com/questions/21900/lower-bound-for-nfa-accepting-3-letter-language">Lower bound for NFA accepting 3 letter language</a>.</p>

<p>Also related that to decide whether the permutation is a single cycle, seems to be hard, see this FOCS paper by Ran Raz and Boris Spieker:
<a href="http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366870-abs.html" rel="nofollow noreferrer">http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366870-abs.html</a>.</p>

<p>So, I am also very interested to learn the answer to this question.</p>

CC BY-SA 3.0
2014-12-22T10:48:07.553Z
When you say that "no matter how we cut the input into two parts" does your argument also rule out reductions when the permutation is split into more than two parts?

For example in the linked paper about counting the number of inversions, there is a reduction from set disjointness, where Alice and Bob have inputs $A, B \subseteq [n]$, and they form permutations $\bar{A_0} B_1 A_0 \bar{B_1}$ and $\bar{A_1} B_0 A_1 \bar{B_0}$. The index 0 or 1 refers to the transformations $2x$ and $2x+1$, and the bar refers to complementing. In other words, what if communication can be multi-round?
László Kozma
CC BY-SA 3.0
2014-12-22T11:44:05.517Z
@laszlo: In this problem it really does not matter how you cut the input as long as you give it to only two players as the parity of the permutation is determined by the number of its cycles (so this is why it differs from the number of inversions).
domotorp
CC BY-SA 3.0
2014-12-22T15:15:00.990Z
Is it easy to see how A can compute a bit from her input using which which B can compute the parity? I see how both A and B know the number of cycles "within their parts". But how do they find the parity of the # of "crossing" cycles?
László Kozma
CC BY-SA 3.0
2014-12-22T16:59:57.760Z
@laszlo: Suppose A's input is something like 1->7, 2->5, 3->8, 4->6. This has the same number of inversions as 1->5, 2->6, 3->8, 4->7. More generally, B knows into what numbers the numbers of A are mapped. Using an even number of inversions, A can permute these numbers into an increasing order, except possibly for the last two. The relation of these last two numbers is the one bit she sends.
domotorp
CC BY-SA 3.0
2015-01-05T10:22:08.600Z
@ domotor: follow-up question - if A gets $a_1, \dots, a_n$, B gets $a_{n+1}, \dots, a_{2n}$, C gets $a_{2n+1}, \dots, a_{3n}$ of a permutation $a$ of $[3n]$, can they establish the parity with $o(n)$ bits of communication?
László Kozma
CC BY-SA 3.0
2015-01-05T15:46:20.567Z
@laszlo: I thought about this myself back then and I could not solve it. One natural conjecture would be that the required number of bits is O(p) if there are p players, but it is just as possible that it is Omega(n) already for 3 players. If you want to, you could ask this as a separate question.
domotorp
CC BY-SA 3.0
2014-12-21T08:15:49.813Z
2014-12-21T14:14:06.250Z
2017-04-13T12:32:28.077Z
domotorp
<p>I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in how much memory a deterministic algorithm should use. Is there any randomized algorithm for the problem?</p>

<p>I know that computing number of inversions in one pass uses $\Theta(n)$ memory. The upper bound can be easily obtained with any BST. The lower bound is presented here: <a href="http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622">http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622</a></p>

<p>Alas, the proof of the lower bound in the paper can not be extended to the parity case (or it's not so obvious to me).</p>

<p>Also I know that computing parity in a little space with random access to a permutation can be done in $O(n \log n)$ time and $O(\log^2 n)$ memory by deterministic algorithm or in $O(n \log n)$ time and $O(\log n)$ memory by randomized one. See <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256</a></p>

<p>The main idea is that the parity of a permutation can be computed by formula $sgn(\pi) = (-1)^{n - c}$, where $c$ is the number of cycles and $n$ is the size. The authors make the cycle decomposition of a permutation. So one can easily compute the number of cycles.</p>

<p>Does anybody know an effective algorithm or lower bound on memory for computing parity in the streaming model? Randomized algorithms better than random coin are interesting to me too. </p>

CC BY-SA 3.0
2014-12-08T13:30:24.940Z
It's interesting. Could you sketch a proof or name a problem, which you reduce to parity?
Vsevolod Oparin
CC BY-SA 3.0
2014-12-08T15:39:29.253Z
@András: Doesn't an O(n) space algorithm work simply by keeping track of which elements have been seen already (say in a bitvector), and then for each new element x adding the parity of the # of yet-to-be-seen elements smaller than x ?
László Kozma
CC BY-SA 3.0
2014-12-08T20:13:56.537Z
@laszlo your $O(n)$ upper bound now seems more convincing to me than my argument for a larger lower bound.
András Salamon
CC BY-SA 3.0
2014-12-09T09:11:41.357Z
One negative result for lower bound. The authors of the first paper provides permutation $\pi = \bar{A_0}B_1A_0\bar{B_1}$ based on two sets $A$ and $B$. They use it to compute whether $A$ and $B$ intersect. Computing parity of the permutation takes only 3 bits of one-way communication. It can be easily obtained by computing rank of corresponding matrix.
Vsevolod Oparin
CC BY-SA 3.0
2014-12-14T20:04:04.613Z
Related: http://stackoverflow.com/questions/20702782/efficiently-determine-the-parity-of-a-permutation
domotorp
<ds.algorithms><permutations><streaming-algorithms>
Computing parity of a permutation in a streaming-fashion way
Vsevolod Oparin
# Computing parity of a permutation in a streaming-fashion way

(Asked by: username_0 on 2014-12-08)

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in how much memory a deterministic algorithm should use. Is there any randomized algorithm for the problem?

I know that computing number of inversions in one pass uses $\Theta(n)$ memory. The upper bound can be easily obtained with any BST. The lower bound is presented here: <http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622>

Alas, the proof of the lower bound in the paper can not be extended to the parity case (or it's not so obvious to me).

Also I know that computing parity in a little space with random access to a permutation can be done in $O(n \log n)$ time and $O(\log^2 n)$ memory by deterministic algorithm or in $O(n \log n)$ time and $O(\log n)$ memory by randomized one. See <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256>

The main idea is that the parity of a permutation can be computed by formula $sgn(\pi) = (-1)^{n - c}$, where $c$ is the number of cycles and $n$ is the size. The authors make the cycle decomposition of a permutation. So one can easily compute the number of cycles.

Does anybody know an effective algorithm or lower bound on memory for computing parity in the streaming model? Randomized algorithms better than random coin are interesting to me too.

**Tags:** ds.algorithms, permutations, streaming-algorithms

> **Comments:**
> **username_0**: It's interesting. Could you sketch a proof or name a problem, which you reduce to parity?  
> **username_1**: @András: Doesn't an O(n) space algorithm work simply by keeping track of which elements have been seen already (say in a bitvector), and then for each new element x adding the parity of the # of yet-to-be-seen elements smaller than x ?  
> **username_2**: @laszlo your $O(n)$ upper bound now seems more convincing to me than my argument for a larger lower bound.  
> **username_0**: One negative result for lower bound. The authors of the first paper provides permutation $\pi = \bar{A_0}B_1A_0\bar{B_1}$ based on two sets $A$ and $B$. They use it to compute whether $A$ and $B$ intersect. Computing parity of the permutation takes only 3 bits of one-way communication. It can be easily obtained by computing rank of corresponding matrix.  
> **username_3**: Related: http://stackoverflow.com/questions/20702782/efficiently-determine-the-parity-of-a-permutation  

---

## 1 answers

### Answer by username_3 on 2014-12-21. Score: 2

I would like to ask everyone not to upvote this, as this is not an answer, but an extended comment, in which I would like to argue why this question did not receive any answers. My main point is, that a communication complexity lower bound won't work. By this, I mean that no matter how we cut the input into two parts and give it to two players, A and B, A can transfer a single bit to B from which he can compute the parity of the permutation. (This follows simply by considering inversions.)

Proofs that use another bound are hard.
See this comment here by Noam Nisan (for the non-deterministic version): [Bounds on the size of the smallest NFA for L\_k-distinct](https://cstheory.stackexchange.com/questions/20468/bounds-on-the-size-of-the-smallest-nfa-for-l-k-distinct#comment57460_20468),

this related question by myself answered by Hermann Gruber which shows that the communication complexity lower bound can be very far from the truth (again in the non-deterministic version)
[Lower bound for NFA accepting 3 letter language](https://cstheory.stackexchange.com/questions/21900/lower-bound-for-nfa-accepting-3-letter-language).

Also related that to decide whether the permutation is a single cycle, seems to be hard, see this FOCS paper by Ran Raz and Boris Spieker:
<http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366870-abs.html>.

So, I am also very interested to learn the answer to this question.

> **Comments:**
> **username_1**: When you say that "no matter how we cut the input into two parts" does your argument also rule out reductions when the permutation is split into more than two parts?  For example in the linked paper about counting the number of inversions, there is a reduction from set disjointness, where Alice and Bob have inputs $A, B \subseteq [n]$, and they form permutations $\bar{A_0} B_1 A_0 \bar{B_1}$ and $\bar{A_1} B_0 A_1 \bar{B_0}$. The index 0 or 1 refers to the transformations $2x$ and $2x+1$, and the bar refers to complementing. In other words, what if communication can be multi-round?  
> **username_3**: @laszlo: In this problem it really does not matter how you cut the input as long as you give it to only two players as the parity of the permutation is determined by the number of its cycles (so this is why it differs from the number of inversions).  
> **username_1**: Is it easy to see how A can compute a bit from her input using which which B can compute the parity? I see how both A and B know the number of cycles "within their parts". But how do they find the parity of the # of "crossing" cycles?  
> **username_3**: @laszlo: Suppose A's input is something like 1->7, 2->5, 3->8, 4->6. This has the same number of inversions as 1->5, 2->6, 3->8, 4->7. More generally, B knows into what numbers the numbers of A are mapped. Using an even number of inversions, A can permute these numbers into an increasing order, except possibly for the last two. The relation of these last two numbers is the one bit she sends.  
> **username_1**: @ domotor: follow-up question - if A gets $a_1, \dots, a_n$, B gets $a_{n+1}, \dots, a_{2n}$, C gets $a_{2n+1}, \dots, a_{3n}$ of a permutation $a$ of $[3n]$, can they establish the parity with $o(n)$ bits of communication?  
> **username_3**: @laszlo: I thought about this myself back then and I could not solve it. One natural conjecture would be that the required number of bits is O(p) if there are p players, but it is just as possible that it is Omega(n) already for 3 players. If you want to, you could ask this as a separate question.  

---

