License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.88
URN: urn:nbn:de:0030-drops-74105
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7410/
Go to the corresponding LIPIcs Volume Portal

Raskin, Mikhail

A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model

pdf-format:
LIPIcs-ICALP-2017-88.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{raskin:LIPIcs:2017:7410,
  author =	{Mikhail Raskin},
  title =	{{A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{88:1--88:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7410},
  URN =		{urn:nbn:de:0030-drops-74105},
  doi =		{10.4230/LIPIcs.ICALP.2017.88},
  annote =	{Keywords: binary counter, data structure, integer representation, bit-probe model, lower bound}
}

Keywords: binary counter, data structure, integer representation, bit-probe model, lower bound
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI