Changing base without losing space

DOI10.1145/1806689.1806771zbMath1293.68118OpenAlexW2167049470MaRDI QIDQ2875186

Yevgeniy Dodis, Mikkel Thorup, Mihai Pǎtraşcu

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806771

zbMATH Keywords

arithmetic codingstreaming algorithmssuccinct data structuresdomain extension of hash functionsprefix-free encoding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Authentication, digital signatures and secret sharing (94A62) Prefix, length-variable, comma-free codes (94A45)

Related Items (17)

How to Share a Secret, Infinitely ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Succinct permutation graphs ⋮ Space-efficient data structure for next/previous larger/smaller value queries ⋮ Succinct representations of permutations and functions ⋮ Succinct representations for (non)deterministic finite automata ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Unnamed Item ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ Succinct representation for (non)deterministic finite automata ⋮ Random Access to High-Order Entropy Compressed Text ⋮ A Survey of Data Structures in the Bitprobe Model

This page was built for publication: Changing base without losing space