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

Author Mikhail Raskin



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.88.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Mikhail Raskin

Cite As Get BibTex

Mikhail Raskin. A Linear Lower Bound for Incrementing a Space-Optimal Integer Representation in the Bit-Probe Model. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 88:1-88:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.88

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.

Subject Classification

Keywords
  • binary counter
  • data structure
  • integer representation
  • bit-probe model
  • lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Prosenjit Bose, Paz Carmi, Dana Jansens, Anil Maheshwari, Pat Morin, and Michiel H. M. Smid. Improved methods for generating quasi-gray codes. In Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings, pages 224-235, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13731-0_22.
  2. Gerth Stølting Brodal, Mark Greve, Vineet Pandey, and Srinivasa Rao Satti. Integer representations towards efficient counting in the bit probe model. J. Discrete Algorithms, 26:34-44, 2014. URL: http://dx.doi.org/10.1016/j.jda.2013.11.001.
  3. Amr Elmasry and Jyrki Katajainen. In-place binary counters. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, pages 349-360, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40313-2_32.
  4. Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. J. ACM, 44(2):257-271, 1997. URL: http://dx.doi.org/10.1145/256303.256309.
  5. Michael L. Fredman. Observations on the complexity of generating quasi-gray codes. SIAM J. Comput., 7(2):134-146, 1978. URL: http://dx.doi.org/10.1137/0207012.
  6. F. Gray. Pulse code communication, March 17 1953. US Patent 2,632,058. URL: https://www.google.com/patents/US2632058.
  7. N. Lauritzen. Concrete Abstract Algebra: From Numbers to Gröbner Bases. Concrete Abstract Algebra: From Numbers to Gröbner Bases. Cambridge University Press, 2003. Google Scholar
  8. M. Ziaur Rahman and J. Ian Munro. Integer representation and counting in the bit probe model. Algorithmica, 56(1):105-127, 2010. URL: http://dx.doi.org/10.1007/s00453-008-9247-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail