A SPECTRAL APPROACH TO LOWER BOUNDS WITH APPLICATIONS TO GEOMETRIC SEARCHING

We establish a nonlinear lower bound for halfplane range searching ove r a group. Specifically, we show that summing up the weights of n (wei ghted) points within n halfplanes requires Omega(n log n) additions an d subtractions. This is the first nontrivial lower bound for range sea rching over a group. By contrast, range searching over a semigroup (wh ich forbids subtractions) is almost completely understood. Our proof h as two parts. First, we develop a general, entropy-based method for re lating the linear circuit complexity of a linear map A to the spectrum of A(inverted perpendicular)A. In the second part of the proof, we de sign a ''high-spectrum'' geometric set system for halfplane range sear ching and, using techniques from discrepancy theory, we estimate the m edian eigenvalue of its associated map. Interestingly, the method also shows that using up to a linear number of help gates cannot help; the se are gates that can compute any bivariate function.