Changing base without losing space

Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
Pages593-602
Number of pages10
DOIs
StatePublished - 2010
Event42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States
Duration: Jun 5 2010Jun 8 2010

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other42nd ACM Symposium on Theory of Computing, STOC 2010
CountryUnited States
CityCambridge, MA
Period6/5/106/8/10

Keywords

  • arithmetic coding
  • domain extension of hash functions
  • prefix-free encoding
  • streaming algorithms
  • succinct data structures

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Changing base without losing space'. Together they form a unique fingerprint.

Cite this