Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR17-040 | 19th March 2017 00:56

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

RSS-Feed




Revision #2
Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
Accepted on: 19th March 2017 00:56
Downloads: 119
Keywords: 


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 \emph{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:
\[\tmed \geq \Omega\left(\frac{n^{\frac{1}{\tins+1}}}{w^2 \cdot \tins^2}\right),\]
where $\tins$ is the number of memory locations accessed during insertions, $\tmed$ 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
\[\tmin + \tdel \geq \Omega\left(\frac{\log n}{\log w + \log \log n}\right),\]
where $\tmin$ is the number of locations accessed to compute the minimum, and $\tdel$ 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
\[\text{either } \tp \geq \Omega\left(\frac{\log n}{\log \log n + \log w}\right), \text{ or } \tins \geq \Omega\left(\frac{\tp\cdot n^{\frac{1}{2(\tp+1)}}}{\log n}\right),\]
were $\tp$ 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\H{o}s and Rado \cite{ErdosR60} together with several kinds of encoding arguments.



Changes to previous version:

Fixed an error in the statement of past work.


Revision #1 to TR17-040 | 19th March 2017 00:48

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





Revision #1
Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
Accepted on: 19th March 2017 00:48
Downloads: 33
Keywords: 


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 \emph{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:
\[\tmed \geq \Omega\left(\frac{n^{\frac{1}{\tins+1}}}{w^2 \cdot \tins^2}\right),\]
where $\tins$ is the number of memory locations accessed during insertions, $\tmed$ 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
\[\tmin + \tdel \geq \Omega\left(\frac{\log n}{\log w + \log \log n}\right),\]
where $\tmin$ is the number of locations accessed to compute the minimum, and $\tdel$ 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
\[\text{either } \tp \geq \Omega\left(\frac{\log n}{\log \log n + \log w}\right), \text{ or } \tins \geq \Omega\left(\frac{\tp\cdot n^{\frac{1}{2(\tp+1)}}}{\log n}\right),\]
were $\tp$ 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\H{o}s and Rado \cite{ErdosR60} together with several kinds of encoding arguments.



Changes to previous version:

Added several references that came to our attention after the initial version was posted, as well as a new proof that proves lower bounds for computing the minimum of a set.


Paper:

TR17-040 | 4th March 2017 18:09

Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers





TR17-040
Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
Publication: 4th March 2017 18:09
Downloads: 220
Keywords: 


Abstract:

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median 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. We prove that any such data structure must satisfy:
$t_m \geq \Omega\left(\frac{n^{\frac{1}{2(t_i+1)}}}{w \cdot t_i}\right),$
where $t_i$ is the number of memory locations accessed during insertions, $t_m$ is the number of memory locations accessed to compute the median, and $w$ is the number of bits stored in each memory location. Our lower bounds are nearly matched by Binary Search Trees.

For the predecessor search problem, where the algorithm 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
$t_p \geq \Omega\left(\frac{\log n}{\log \log n + \log w}\right)$ or $t_i \geq \Omega\left(\frac{t_p\cdot n^{\frac{1}{2(t_p+1)}}}{\log n}\right)$,
were $t_p$ is the number of locations accessed to compute predecessors. Again, these bounds prove that Binary Search Trees have essentially optimal parameters for the predecessor search problem.

Our results follow from a novel application of the Sunflower Lemma of Erdos and Rado to these questions.



ISSN 1433-8092 | Imprint