Computing parity needs lots of memory pattern detection very little
Parity and Pattern Detection in Permutation Streams
Data Structures and Algorithms
Summary
This paper looks at how much memory is needed to process lists of numbers arriving one by one. It finds that figuring out if the order is even or odd (parity) needs a lot of memory, about the size of the entire list. But spotting certain small arrangements of numbers, called patterns of length three, can be done with very little memory. This answers earlier questions about what makes some problems easy or hard in this setting. The findings also show that checking certain ways of walking through tree structures can use very little memory in a similar streaming way.
permutationstreaming algorithmsspace complexityparitypattern detectionrandomizationlogarithmic memorypermutation patternsbinary search tree traversal
Authors
Mark Braverman, Or Zamir
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 $Θ(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 $Θ(\log n)$ for monotone patterns and patterns of length at most three, and $Θ(n)$ for every other pattern. As a consequence, we observe that we can verify BST traversals in streaming with logarithmic memory.