2018/08/10 by Dekel Tsur, Tsur, Dekel
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1808.03658
openalex publication_date 2018/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of storing the minimum number of bits required to answer next/previous larger/smaller value queries on an array A of n numbers, without storing A. We show that these queries can be answered by storing at most 3.701 n bits. Our result improves the result of Jo and Satti [TCS 2016] that gives an upper bound of 4.088n bits for this problem.