Abstract
We prove new cellprobe 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 nonadaptively 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 nonadaptively and compute the minimum nonadaptively, 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 nonadaptively, 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.
BibTeX  Entry
@InProceedings{natarajanramamoorthy_et_al:LIPIcs:2018:8862,
author = {Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao},
title = {{Lower Bounds on NonAdaptive Data Structures Maintaining Sets of Numbers, from Sunflowers}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {27:127:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8862},
URN = {urn:nbn:de:0030drops88625},
doi = {10.4230/LIPIcs.CCC.2018.27},
annote = {Keywords: Nonadaptive data structures, Sunflower lemma}
}
Keywords: 

Nonadaptive data structures, Sunflower lemma 
Collection: 

33rd Computational Complexity Conference (CCC 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 