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
SN - 0272-5428
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
T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science
Y2 - 20 November 1994 through 22 November 1994
ER -