Two BSP algorithms for Bruhat decomposition achieve O(n^3/p) computation, O(n^2/p^(2/3)) communication, and a tunable synchronization cost, with the strip-recursive variant matching the best known trade-off for LU decomposition.
A pattern theorem for random sorting networks
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
A sorting network is a shortest path from 12..n to n..21 in the Cayley graph of the symmetric group S(n) generated by nearest-neighbor swaps. A pattern is a sequence of swaps that forms an initial segment of some sorting network. We prove that in a uniformly random n-element sorting network, any fixed pattern occurs in at least cn^2 disjoint space-time locations, with probability tending to 1 exponentially fast as n tends to infinity. Here c is a positive constant which depends on the choice of pattern. As a consequence, the probability that the uniformly random sorting network is geometrically realizable tends to 0.
fields
cs.DS 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Communication-efficient parallel Bruhat decomposition
Two BSP algorithms for Bruhat decomposition achieve O(n^3/p) computation, O(n^2/p^(2/3)) communication, and a tunable synchronization cost, with the strip-recursive variant matching the best known trade-off for LU decomposition.