TIME: 1:30-2:20 pm, May 15, 2007 PLACE: CSE 403 SPEAKER: Mihai Patrascu M.I.T. TITLE: Lower Bounds for 2-Dimensional Range Counting ABSTRACT: 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].