Parity and Pattern Detection in Permutation Streams

Abstract

Consider a permutation of $[n]$ whose values arrive one at a time. We resolve two questions about the space needed to decide natural properties of such input: First, computing the parity of the permutation requires $\Theta (n)$ bits, even with randomization and constant error, and a constant number of passes. Second, every permutation pattern of length three can be detected deterministically in one pass using $O(\log n)$ bits. Together with the 2026 lower bounds of Berendsohn, this completes the classification of fixed permutation patterns; The optimal space complexity is $\Theta (\log n)$ for monotone patterns and patterns of length at most three, and $\Theta (n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.