Dynamic data structures for twin-ordered matrices
Lists
Only you see this
Abstract
We present a dynamic data structure for representing binary $n\times n$ matrices that are $d$-twin-ordered, for a~fixed parameter $d$. Our structure supports cell queries and single-cell updates both in $\Oh(\log \log n)$ expected worst case time, while using $\Oh_d(n)$ memory; here, the $\Oh_d(\cdot)$ notation
BibTeX
@misc{bosek2026dynamic,
author = {Bartłomiej Bosek and Jadwiga Czyżewska and Evangelos Kipouridis and Wojciech Nadara and Michał Pilipczuk and Karol Węgrzycki and Anna Zych-Pawlewicz},
title = {{Dynamic data structures for twin-ordered matrices}},
year = {2026},
eprint = {2602.18770},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2602.18770},
}Loading related content...