Cell-Probe Lower Bounds for Prefix Sums - Computer Science > Computational ComplexityReportar como inadecuado




Cell-Probe Lower Bounds for Prefix Sums - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We prove that to store n bits x so that each prefix-sum query Sumi :=sum {k < i} x k can be answered by non-adaptively probing q cells of log nbits, one needs memory > n + n-log^{Oq} n. Our bound matches a recent upperbound of n + n-log^{Omegaq} n by Patrascu FOCS 2008, also non-adaptive. Wealso obtain a n + n-log^{2^{Oq}} n lower bound for storing a string ofbalanced brackets so that each Matchi query can be answered by non-adaptivelyprobing q cells. To obtain these bounds we show that a too efficient datastructure allows us to break the correlations between query answers.



Autor: Emanuele Viola

Fuente: https://arxiv.org/







Documentos relacionados