Computing parity of a permutation in a streaming-fashion way 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.
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,

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.

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.