A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Documents

DOI

  • Mikhail Raskin

We present the first linear lower bound for the number of bits required to be accessed in the worst case to increment an integer in an arbitrary space-optimal binary representation. The best previously known lower bound was logarithmic. It is known that a logarithmic number of read bits in the worst case is enough to increment some of the integer representations that use one bit of redundancy, therefore we show an exponential gap between space-optimal and redundant counters. Our proof is based on considering the increment procedure for a space optimal counter as a permutation and calculating its parity. For every space optimal counter, the permutation must be odd, and implementing an odd permutation requires reading at least half the bits in the worst case. The combination of these two observations explains why the worst-case space-optimal problem is substantially different from both average-case approach with constant expected number of reads and almost space optimal representations with logarithmic number of reads in the worst case.

Original languageEnglish
Title of host publication44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
EditorsIoannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl
Number of pages12
Volume80
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year2017
Pages88:1--88:12
Article number88
ISBN (Electronic)9783959770415
DOIs
Publication statusPublished - 2017
Event44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland
Duration: 10 Jul 201714 Jul 2017

Conference

Conference44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
LandPoland
ByWarsaw
Periode10/07/201714/07/2017
SponsorAICA, Austrian, Department of Informatics, Sapienza University of Rome, Facebook, Microsoft, Microsoft Research
SeriesLeibniz International Proceedings in Informatics
Volume80
ISSN1868-8969

    Research areas

  • Binary counter, Bit-probe model, Data structure, Integer representation, Lower bound

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 118169313