TY - JOUR

T1 - A spectral approach to lower bounds

AU - Chazelle, Bernard

N1 - Funding Information:
This work was supported in part by NSF Grant CCR-93-01254 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc.
Publisher Copyright:
© 1994 IEEE

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85100330410&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100330410&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1994.365725

DO - 10.1109/SFCS.1994.365725

M3 - Conference article

AN - SCOPUS:85100330410

SP - 674

EP - 682

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SN - 0272-5428

T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science

Y2 - 20 November 1994 through 22 November 1994

ER -