A spectral approach to lower bounds

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations


We establish a nonlinear lower bound for halfplane range searching over a group. Specifically, we show that summing up the weights of n (weighted) points within n halfplanes requires Ω(n log n) additions and subtractions. This is the first nontrivial lower bound for range searching over a group. By constrast, range searching over a semigroup (which forbids subtractions) is almost completely understood. Our proof has two parts: First, we develop a general, entropy-based, method for relating the linear circuit complexity of a linear map A to the spectrum of ATA. In the second part of the proof, we design a "high-spectrum" geometric set system and, using techniques from discrepancy theory, we estimate the median eigenvalue of its associated map. Interestingly, the method also shows that using up to a linear number of help gates cannot help; these are gates that can compute any bivariate function. The best feature of our method is that it is very general. With any instance of range searching we associate a quadratic form: any lower bound on the mid-range of its spectrum implies a lower bound on the complexity of that range searching problem. The main drawback of our approach is that it (probably) yields weak lower bounds. Another shortcoming is that the method does not seem to generalize to range searching over rings or fields.

Original languageEnglish (US)
Pages (from-to)674-682
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1994
Externally publishedYes
EventProceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA
Duration: Nov 20 1994Nov 22 1994

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'A spectral approach to lower bounds'. Together they form a unique fingerprint.

Cite this