Cell-Probe Lower Bounds for Bit Stream Computation

Authors Raphaël Clifford, Markus Jalsenius, Benjamin Sach



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.31.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Raphaël Clifford
Markus Jalsenius
Benjamin Sach

Cite AsGet BibTex

Raphaël Clifford, Markus Jalsenius, and Benjamin Sach. Cell-Probe Lower Bounds for Bit Stream Computation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.31

Abstract

We revisit the complexity of online computation in the cell probe model. We consider a class of problems where we are first given a fixed pattern F of n symbols and then one symbol arrives at a time in a stream. After each symbol has arrived we must output some function of F and the n-length suffix of the arriving stream. Cell probe bounds of Omega(delta lg n/w) have previously been shown for both convolution and Hamming distance in this setting, where delta is the size of a symbol in bits and w in Omega(lg n) is the cell size in bits. However, when delta is a constant, as it is in many natural situations, the existing approaches no longer give us non-trivial bounds. We introduce a lop-sided information transfer proof technique which enables us to prove meaningful lower bounds even for constant size input alphabets. Our new framework is capable of proving amortised cell probe lower bounds of Omega(lg^2 n/(w lg lg n)) time per arriving bit. We demonstrate this technique by showing a new lower bound for a problem known as pattern matching with address errors or the L_2-rearrangement distance problem. This gives the first non-trivial cell probe lower bound for any online problem on bit streams that still holds when the cell size is large.
Keywords
  • Cell-probe lower bounds
  • algorithms
  • data streaming

Metrics

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

References

  1. A. Amir, Y. Aumann, G. Benson, A. Levy, O. Lipsky, E. Porat, S. Skiena, and U. Vishne. Pattern matching with address errors: rearrangement distances. In SODA'06: Proc. 17superscriptth ACM-SIAM Symp. on Discrete Algorithms, pages 1221-1229. ACM Press, 2006. Google Scholar
  2. A. Amir, Y. Aumann, G. Benson, A. Levy, O. Lipsky, E. Porat, S. Skiena, and U. Vishne. Pattern matching with address errors: Rearrangement distances. Journal of Computer System Sciences, 75(6):359-370, 2009. Google Scholar
  3. R. Clifford and M. Jalsenius. Lower bounds for online integer multiplication and convolution in the cell-probe model. In ICALP'11: Proc. 38superscriptth International Colloquium on Automata, Languages and Programming, pages 593-604, 2011. URL: http://arxiv.org/abs/1101.0768.
  4. R. Clifford, M. Jalsenius, and B. Sach. Tight cell-probe bounds for online hamming distance computation. In SODA'13: Proc. 24superscriptth ACM-SIAM Symp. on Discrete Algorithms, pages 664-674, 2013. URL: http://arxiv.org/abs/1207.1885.
  5. R. Clifford, M. Jalsenius, and B. Sach. Cell-probe bounds for online edit distance and other pattern matching problems. In SODA'15: Proc. 26superscriptth ACM-SIAM Symp. on Discrete Algorithms, 2015. URL: http://arxiv.org/abs/1407.6559.
  6. R. Clifford and B. Sach. Pattern matching in pseudo real-time. Journal of Discrete Algorithms, 9(1):67-81, 2011. Google Scholar
  7. M. Fredman. Observations on the complexity of generating quasi-Gray codes. SIAM Journal on Computing, 7(2):134-146, 1978. Google Scholar
  8. M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In STOC'89: Proc. 21superscriptst Annual ACM Symp. Theory of Computing, pages 345-354, 1989. Google Scholar
  9. K. Green Larsen. The cell probe complexity of dynamic range counting. In STOC'12: Proc. 44superscriptth Annual ACM Symp. Theory of Computing, pages 85-94, 2012. Google Scholar
  10. K. Green Larsen. Higher cell probe lower bounds for evaluating polynomials. In FOCS'12: Proc. 53superscriptrd Annual Symp. Foundations of Computer Science, pages 293-301, 2012. Google Scholar
  11. M. Minsky and S. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969. Google Scholar
  12. M. Pǎtraşcu. Lower bound techniques for data structures. PhD thesis, MIT, 2008. Google Scholar
  13. M. Pǎtraşcu and E. D. Demaine. Tight bounds for the partial-sums problem. In SODA'04: Proc. 15superscriptth ACM-SIAM Symp. on Discrete Algorithms, pages 20-29, 2004. Google Scholar
  14. M. Pătraşcu and E. D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 35(4):932-963, 2006. Google Scholar
  15. R.Clifford, A. Grønlund, and K. Green Larsen. New unconditional hardness results for dynamic and online problems. In FOCS'15: Proc. 56superscriptth Annual Symp. Foundations of Computer Science, pages 1089-1107, 2015. Google Scholar
  16. A. Yao. Probabilistic computations: Toward a unified measure of complexity. In FOCS'77: Proc. 18superscriptth Annual Symp. Foundations of Computer Science, pages 222-227, 1977. Google Scholar
  17. A. Yao. Should tables be sorted? Journal of the ACM, 28(3):615-628, 1981. Google Scholar
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