Raskin, Mikhail
A Linear Lower Bound for Incrementing a SpaceOptimal Integer Representation in the BitProbe Model
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 spaceoptimal 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 spaceoptimal 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 worstcase spaceoptimal problem is substantially different from both averagecase 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 SpaceOptimal Integer Representation in the BitProbe Model}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {88:188:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7410},
URN = {urn:nbn:de:0030drops74105},
doi = {10.4230/LIPIcs.ICALP.2017.88},
annote = {Keywords: binary counter, data structure, integer representation, bitprobe model, lower bound}
}
2017
Keywords: 

binary counter, data structure, integer representation, bitprobe model, lower bound 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 