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