TIME: 1:30-2:20 pm,  May 15, 2007


SPEAKER: Mihai Patrascu

TITLE:  Lower Bounds for 2-Dimensional Range Counting

Suppose you have a data base of n employees, for which you know the
age and salaray. Range counting queries ask questions of the form "how
many employees are between 30 and 40 years of age, and earn between
60K and 70K?"

We show that any data structure of size at most n*poly(log n) requires
query time a least Omega(lg n / lglg n). This is tight, and represents
an exponential improvement over previous bounds. In particular, our
result implies the first near-logarithmic lower bound for *any*
problem in the so-called group model. Obtaining such a bound has been
regarded as an important challenge at least since [Fredman, JACM 1982]
and [Chazelle, FOCS 1986].