CS Paper Radar

Parity and Pattern Detection in Permutation Streams

Mark Braverman, Or Zamir

cs.DS ·submitted 2026-09-08 17:18 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231

cs.DM math.COcs.DScs.LO ·2026-09-14 ·Henning Arnór Skeggi Úlfarsson
code/data similarity 0.65
Abstract · 36 pages, 4 figures, 1 table. v2: revised and shortened exposition, corrected account of prior work, the first 151 terms tabulated, a proved…

We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance $3.5\cdot10^{-5}$ of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.

0.32

Optimal Pattern-Avoidance Bounds for Binary Search Trees

cs.DS ·2026-11-15 ·Anita Dürr, Arturo Merino, Karol Węgrzycki, Sorrachai Yingchareonthawornchai
theorycode/datahot direction similarity 0.63
Abstract · 37 pages. Submitted to STOC 2027. Publicly available at https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/906.pdf

Self-adjusting binary search trees (BSTs) perform better than balanced BSTs if the access sequence has additional structure. For example, splay trees serve a sequential access sequence in linear time. Pattern avoidance captures regularity in an access sequence and unifies several classic examples of efficient BST access, such as deque and traversal sequences. A central question is how well a BST algorithm can exploit a pattern-avoiding access sequence. We present an online BST algorithm that serves an access sequence avoiding a permutation pattern $π$ in linear time, matching the information-theoretic lower bound. The algorithm does not need to know that pattern $π$ a priori. Our results answer an open problem asked by [Kozma 2016, Problem 44, strong variant]. Previously, the best known offline bound was optimal only for constant-size patterns [Berendsohn, Kozma, and Opler, STOC'24], and the best known online bound was superlinear [Chalermsook, Pettie, Yingchareonthawornchai, SODA'24] even for a constant-size pattern. As a corollary, our BST algorithm yields an optimal sorting algorithm for a pattern-avoiding sequence that supports online insertions. Previously, an optimal sorting algorithm was achieved using a mergesort-like approach [Opler, FOCS'24] in a batch setting. A key technique is to apply recursive split decomposition [Chalermsook, Chuzhoy, Saranurak, ToC'23] jointly in time and space, along with the Marcus-Tardos proof of the Stanley-Wilf conjecture. We show that the framework can be implemented online using $k$-finger BSTs, which is of independent interest. Finally, this framework also yields a constant-factor-approximation FPT algorithm in the offline setting.

0.41

A Binary Search Tree with the Unified Bound

cs.DS ·2026-11-12 ·Yang Cao, Haoran Qi, Hanzhi Wang
theory similarity 0.61
Abstract

We give a deterministic online binary search tree (BST) that satisfies the unified bound of Iacono [SODA 2001], which subsumes the working-set and dynamic-finger bounds: it serves every sequence $X$ of $m$ searches on $n$ keys at total cost $O(m+\mathrm{UB}(X))$, and every single search at cost $O(\log n)$. Previously, no BST was known to satisfy the unified bound, even offline. As a consequence, the dynamic optimality conjecture implies Iacono's conjecture that splay trees satisfy the unified bound. We also show that the unified bound is $O((m+n)(1+\log c_σ))$ on every sequence of searches that avoids a fixed permutation $σ$, where $c_σ$ is the Füredi-Hajnal limit of $σ$. Hence every BST that satisfies the unified bound, including ours, serves such sequences at this cost. For permutations this bound is tight, and it improves the previous upper bound $O(nc_σ^2)$ on the optimal cost, due to Berendsohn, Kozma and Opler [STOC 2024]. Finally, we extend the tree to support insertions and deletions: a sequence $X$ of $m$ operations, starting from $n_0$ keys, costs $O(n_0+m+\mathrm{UB}(X))$ in total, where $\mathrm{UB}$ is now the extension of the unified bound to insertions and deletions by Bădoiu, Cole, Demaine and Iacono [TCS 2007]. Hence, if splay trees are dynamically optimal for searches, insertions and deletions, then they serve every such sequence at this total cost as well.

0.25

Heap-type permutation generation with a prescribed final arrangement

cs.DM math.COcs.DS ·2026-11-17 ·Luís M. S. Russo
theory similarity 0.61
Abstract · 22 pages. Software archived at https://doi.org/10.5281/zenodo.24311260

Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.

0.41

Correcting Burst Errors with Applications to DNA-Based Data Storage

cs.IT ·2026-10-11 ·Yuan-Pon Chen, Olgica Milenkovic
theory similarity 0.58
Abstract · 19 pages, 2 figures, 3 tables

We introduce the problem of permutation burst error-correction, motivated by applications in molecular data storage with nanopore sequencing read platforms. A permutation burst of length $k$ is an error that affects a substring of length $k$ of a string of length $n$ by permuting its entries. Permutation burst errors can be corrected using classical burst error-correcting codes, such as Fire and Reed-Solomon codes. Here, we study how to reduce the redundancy of these classical codes by taking into account that the burst error preserves the weight of the substring. In addition, we further restrict our model to handle cyclic permutation bursts only, which are of independent practical and mathematical interest. Our main results include proving/establishing the following: a) for $k=o(\sqrt{n}),$ the redundancy of any permutation burst error correcting code is at least $\log n-k+\log \binom{2k-2}{k-2}+o(1).$ This result follows from McDiarmid's concentration bound; b) for $k \geq 9$ and $k=o\left(\sqrt{\frac{n}{\log n}}\right)$, the redundancy of any cyclic permutation burst error correcting code is at least $\log n +\log (k(k-1)-56)-\log\,80+o(1).$ c) the asymptotic redundancy upper bounds for the two types of substring errors that are twice the lower bound; d) constructions for both permutation burst and cyclic permutation burst errors that involve Varshamov-Tenegoltz type constraints or represent generalizations and extensions of Fire and other codes. In particular, we exhibit polynomially encodable and decodable codes that can correct cyclic bursts of length $\leq k$ using $\log n + k + 49\log k + O(\log \log k)$ redundant bits.

0.21

Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori

cs.DM math.CO ·2026-09-23 ·Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams
similarity 0.58
Abstract

A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.

0.23

Enumeration Complexity of Permutation Classes

cs.CC math.CO ·2026-10-27 ·Manuel Bodirsky, Mohamed Elsheikh
theory similarity 0.58
Abstract

We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $B$. However, our main notion of efficiency is polynomial delay. We use the insert-maximum tree as a search tree, in which permutations are built by repeatedly inserting a new maximum while preserving pattern avoidance. This leads to the \emph{insert-maximum extension problem}, which asks if a given permutation has an avoiding descendant at a specified depth. An algorithm for this problem can prune branches that cannot reach the target length. Hence, if this problem is in P, we obtain polynomial-delay enumeration. To investigate this problem, we introduce and study \emph{pockets}, the maximal finite subtrees of the insert-maximum tree. For fixed $B$, if there is a polynomial $p$ such that every pocket rooted at $ρ$ has at most $p(|ρ|)$ nodes, then the extension problem is solvable in polynomial time and enumeration has polynomial delay. In particular, a bound on pocket depth depending only on $B$ suffices. We prove such a bound if the class is well-quasi-ordered, has a regular insertion encoding, or if $B$ omits one of the three maximum-position types: leftmost, interior, or rightmost. We also prove that extension is in NP for every fixed $B$, even with binary-encoded target depth. On the negative side, we construct a fixed set of $55$ forbidden patterns for which extension is NP-complete. Consequently, enumerating valid extensions from a given starting permutation cannot have polynomial delay unless P=NP. This also answers a question of Hanika by showing that the forbidden permutation constraint satisfaction problem can be NP-complete for a fixed forbidden set.

0.08

Communication-Oblivious Permutation and Sorting

cs.DS ·2026-10-29 ·Qi Dong, Yilei Wang, Ke Yi
theory similarity 0.57
Abstract

With the help of secure hardware such as trusted execution environments (TEEs), private data can be uploaded and computed in untrusted cloud clusters, so that an adversary controlling the cloud can only see the data in encrypted form. However, the communication pattern between the processors may still reveal sensitive information about the data, so it is important to develop parallel algorithms in the BSP model whose communication pattern is independent of the input data, a property known as \textit{communication obliviousness}. In this paper, we study such algorithms for three fundamental problems: permutation, sorting, and 0-1 sorting. For the first two problems, we prove a tight (up to lower-order terms) communication complexity of $(2-2/p)n\pm o(n)$. Here, $p$ is the number of processors and $n$ is the input size, assuming $2\le p$ and $p=o(n^{1/3})$. Our lower bound holds regardless of the number of rounds and local memory size, while for balanced permutation and sorting the upper bound is achieved in a constant number of rounds with load at most $n/p+o(n/p)$. For 0-1 sorting, we also derive a tight communication complexity of $C_{\mathrm{cut}}(p) \cdot n \pm o(n)$, where $C_{\mathrm{cut}}(p)$ is the optimal value of a linear program parameterized by $p$. Although there appears to be no closed-form for $C_{\mathrm{cut}}(p)$, we show that it is strictly smaller than $2-2/p$ for all $p\ge 3$, thus separating 0-1 sorting from general sorting in terms of their communication complexity.

0.28