17
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ It's interesting. Could you sketch a proof or name a problem, which you reduce to parity? $\endgroup$
    – Vsevolod Oparin
    Dec 8, 2014 at 13:30
  • 4
    $\begingroup$ @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 ? $\endgroup$
    – László Kozma
    Dec 8, 2014 at 15:39
  • 1
    $\begingroup$ @laszlo your $O(n)$ upper bound now seems more convincing to me than my argument for a larger lower bound. $\endgroup$
    – András Salamon
    Dec 8, 2014 at 20:13
  • $\begingroup$ 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. $\endgroup$
    – Vsevolod Oparin
    Dec 9, 2014 at 9:11
  • 1
    $\begingroup$ Related: stackoverflow.com/questions/20702782/… $\endgroup$
    – domotorp
    Dec 14, 2014 at 20:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – László Kozma
    Dec 22, 2014 at 10:48
  • $\begingroup$ @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). $\endgroup$
    – domotorp
    Dec 22, 2014 at 11:44
  • $\begingroup$ 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? $\endgroup$
    – László Kozma
    Dec 22, 2014 at 15:15
  • 2
    $\begingroup$ @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. $\endgroup$
    – domotorp
    Dec 22, 2014 at 16:59
  • $\begingroup$ @ 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? $\endgroup$
    – László Kozma
    Jan 5, 2015 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.