TY - GEN
T1 - Changing base without losing space
AU - Dodis, Yevgeniy
AU - Patrascu, Mihai
AU - Thorup, Mikkel
PY - 2010
Y1 - 2010
N2 - We describe a simple, but powerful local encoding technique, implying two surprising results: 1. We show how to represent a vector of n values from ∑ using ⌈ n log2 ∑⌉ bits, such that reading or writing any entry takes O(1) time. This demonstrates, for instance, an "equivalence" between decimal and binary computers, and has been a central toy problem in the field of succinct data structures. Previous solutions required space of n log2 ∑ + n/logO(1) n bits for constant access. 2. Given a stream of n bits arriving online (for any n, not known in advance), we can output a*prefix-free* encoding that uses n + log2 n + O(loglog n) bits. The encoding and decoding algorithms only require O(log n) bits of memory, and run in constant time per word. This result is interesting in cryptographic applications, as prefix-free codes are the simplest counter-measure to extensions attacks on hash functions, message authentication codes and pseudorandom functions. Our result refutes a conjecture of [Maurer, Sjödin 2005] on the hardness of online prefix-free encodings.
AB - We describe a simple, but powerful local encoding technique, implying two surprising results: 1. We show how to represent a vector of n values from ∑ using ⌈ n log2 ∑⌉ bits, such that reading or writing any entry takes O(1) time. This demonstrates, for instance, an "equivalence" between decimal and binary computers, and has been a central toy problem in the field of succinct data structures. Previous solutions required space of n log2 ∑ + n/logO(1) n bits for constant access. 2. Given a stream of n bits arriving online (for any n, not known in advance), we can output a*prefix-free* encoding that uses n + log2 n + O(loglog n) bits. The encoding and decoding algorithms only require O(log n) bits of memory, and run in constant time per word. This result is interesting in cryptographic applications, as prefix-free codes are the simplest counter-measure to extensions attacks on hash functions, message authentication codes and pseudorandom functions. Our result refutes a conjecture of [Maurer, Sjödin 2005] on the hardness of online prefix-free encodings.
KW - arithmetic coding
KW - domain extension of hash functions
KW - prefix-free encoding
KW - streaming algorithms
KW - succinct data structures
UR - http://www.scopus.com/inward/record.url?scp=77954732809&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954732809&partnerID=8YFLogxK
U2 - 10.1145/1806689.1806771
DO - 10.1145/1806689.1806771
M3 - Conference contribution
AN - SCOPUS:77954732809
SN - 9781605588179
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 593
EP - 602
BT - STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
T2 - 42nd ACM Symposium on Theory of Computing, STOC 2010
Y2 - 5 June 2010 through 8 June 2010
ER -