Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers

Authors Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao



PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.27.pdf
  • Filesize: 0.66 MB
  • 16 pages

Document Identifiers

Author Details

Sivaramakrishnan Natarajan Ramamoorthy
  • Paul G. Allen School for Computer Science & Engineering, University of Washington, Seattle, USA
Anup Rao
  • Paul G. Allen School for Computer Science & Engineering, University of Washington, Seattle, USA

Cite AsGet BibTex

Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao. Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.27

Abstract

We prove new cell-probe lower bounds for dynamic data structures that maintain a subset of {1,2,...,n}, and compute various statistics of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of the memory. For any such data structure that can compute the median of the set, we prove that: t_{med} >= Omega(n^{1/(t_{ins}+1)}/(w^2 * t_{ins}^2)), where t_{ins} is the number of memory locations accessed during insertions, t_{med} is the number of memory locations accessed to compute the median, and w is the number of bits stored in each memory location. When the data structure is able to perform deletions non-adaptively and compute the minimum non-adaptively, we prove t_{min} + t_{del} >= Omega(log n /(log w + log log n)), where t_{min} is the number of locations accessed to compute the minimum, and t_{del} is the number of locations accessed to perform deletions. For the predecessor search problem, where the data structure is required to compute the predecessor of any element in the set, we prove that if computing the predecessors can be done non-adaptively, then either t_{pred} >= Omega(log n/(log log n + log w)), or t_{ins} >= Omega(n^{1/(2(t_{pred}+1))}), where t_{pred} is the number of locations accessed to compute predecessors. These bounds are nearly matched by Binary Search Trees in some range of parameters. Our results follow from using the Sunflower Lemma of Erdös and Rado [Paul Erdös and Richard Rado, 1960] together with several kinds of encoding arguments.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cell probe models and lower bounds
Keywords
  • Non-adaptive data structures
  • Sunflower lemma

Metrics

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

References

  1. Miklós Ajtai. A lower bound for finding predecessors in yao’s call probe model. Combinatorica, 8(3), 1988. Google Scholar
  2. Noga Alon and Ravi B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1-22, 1987. Google Scholar
  3. Noga Alon and Uriel Feige. On the power of two, three and four probes. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009. SIAM, 2009. Google Scholar
  4. Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem and related problems. JCSS: Journal of Computer and System Sciences, 65, 2002. Google Scholar
  5. Paul Beame, Vincent Liew, and Mihai Patrascu. Finding the median (obliviously) with bounded space. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 103-115, 2015. Google Scholar
  6. Joseph Boninger, Joshua Brody, and Owen Kephart. Non-adaptive data structure bounds for dynamic predecessor. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, pages 20:1-20:12, 2017. Google Scholar
  7. Gerth Stølting Brodal, Shiva Chaudhuri, and Jaikumar Radhakrishnan. The randomized complexity of maintaining the minimum. In SWAT: Scandinavian Workshop on Algorithm Theory, 1996. Google Scholar
  8. Joshua Brody and Kasper Green Larsen. Adapt or die: Polynomial lower bounds for non-adaptive dynamic data structures. Theory of Computing, 11:471-489, 2015. Google Scholar
  9. Amit Chakrabarti, T. S. Jayram, and Mihai Patrascu. Tight lower bounds for selection in randomly ordered streams. In Proc. 19th Symp. on Discrete Algorithms (SODA), pages 720-729. ACM/SIAM, 2008. Google Scholar
  10. Timothy M. Chan. Comparison-based time-space lower bounds for selection. ACM Trans. Algorithms, 6(2), 2010. Google Scholar
  11. Paul Erdős and Richard Rado. Intersection theorems for systems of sets. Journal of London Mathematical Society, 35:85-90, 1960. Google Scholar
  12. 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.
  13. Michael Fredman and Michael Saks. The cell probe complexity of dynamic data structures. In STOC: ACM Symposium on Theory of Computing (STOC), 1989. Google Scholar
  14. Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. JCSS: Journal of Computer and System Sciences, 47, 1993. Google Scholar
  15. Anna Gál and Peter Bro Miltersen. The cell probe complexity of succinct data structures. Theor. Comput. Sci., 379(3):405-417, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.02.047.
  16. Mohit Garg and Jaikumar Radhakrishnan. Set membership with non-adaptive bit probes. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 38:1-38:13, 2017. Google Scholar
  17. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In STOC: ACM Symposium on Theory of Computing (STOC), 2000. Google Scholar
  18. Kasper Green Larsen. The cell probe complexity of dynamic range counting. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 85-94, 2012. Google Scholar
  19. Peter Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. 57:37-49, 1 1998. Google Scholar
  20. Peter Bro Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proceedings of the 26th Annual Symposium on the Theory of Computing, pages 625-634, New York, 1994. ACM Press. Google Scholar
  21. J. Ian Munro and Venkatesh Raman. Selection from read-only memory and sorting with minimum data movement. TCS: Theoretical Computer Science, 165, 1996. Google Scholar
  22. Rina Panigrahy, Kunal Talwar, and Udi Wieder. Lower bounds on near neighbor search via metric expansion. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pages 805-814, Washington, DC, USA, 2010. IEEE Computer Society. Google Scholar
  23. Mihai Pǎtraşcu. Lower bounds for 2-dimensional range counting. In Proc. 39th ACM Symposium on Theory of Computing (STOC), pages 40-46, 2007. Google Scholar
  24. Mihai Pǎtraşcu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 35(4):932-963, 2006. See also STOC'04, SODA'04. Google Scholar
  25. Mihai Patrascu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 232-240, 2006. Google Scholar
  26. Mihai Pǎtraşcu and Mikkel Thorup. Don't rush into a union: Take time to find your roots. In Proc. 43rd ACM Symposium on Theory of Computing (STOC), pages 559-568, 2011. See also arXiv:1102.1783. Google Scholar
  27. Mihai Patrascu and Mikkel Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 166-175, 2014. Google Scholar
  28. Pranab Sen and Srinivasan Venkatesh. Lower bounds for predecessor searching in the cell probe model. J. Comput. Syst. Sci, 74(3):364-385, 2008. Google Scholar
  29. Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80-82, 1977. Google Scholar
  30. Omri Weinstein and Huacheng Yu. Amortized dynamic cell-probe lower bounds from four-party communication. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 305-314, 2016. Google Scholar
  31. Dan E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Information Processing Letters, pages 81-84, 1983. Google Scholar
  32. Andrew Yao. Should tables be sorted? JACM: Journal of the ACM, 28, 1981. Google Scholar
  33. Huacheng Yu. Cell-probe lower bounds for dynamic problems via a new communication model. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 362-374, 2016. 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