{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:57Z","timestamp":1787337477659,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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 $\\Omega(n\\log n)$ additions and subtractions. This is the first nontrivial lower bound for range searching over a group. By contrast, range searching over a semigroup (which forbids subtractions) is almost completely understood.<\/jats:p>\n                  <jats:p>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 $A^\\top\\!A$. In the second part of the proof, we design a \"high-spectrum\" geometric set system for halfplane range searching 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.<\/jats:p>","DOI":"10.1137\/s0097539794275665","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"545-556","source":"Crossref","is-referenced-by-count":13,"title":["A Spectral Approach to Lower Bounds with Applications to Geometric Searching"],"prefix":"10.1137","volume":"27","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02123006"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0219074"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Amir, R. Beigel, and W. Gasarch,\n                      Some connections between bounded query classes and nonuniform complexity\n                      , 5th Annual Structure in Complexity Theory Conference, 1990, pp. 232\u2013243.","DOI":"10.1109\/SCT.1990.113971"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1999.2442"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Ravi Boppana, Michael Sipser, The complexity of finite functions, Elsevier, Amsterdam, 1990, 757\u20138041127180","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. Y. Cai,\n                      Lower bounds for constant depth circuits in the presence of help bits\n                      , Proc. 30th Annual Symp. Foundation Comput. Sci., 1989, pp. 532\u2013537.","DOI":"10.1109\/SFCS.1989.63530"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-1001852-0"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Bernard Chazelle, Geometric discrepancy revisited, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 392\u20133991328436","DOI":"10.1109\/SFCS.1993.366848"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"B. Chazelle,\n                      Computational geometry: A retrospective\n                      , In Computing in Euclidean Geometry, 2nd ed., D.\u2010Z. Du and F. Hwang, eds., World Scientific Press, 1995, pp. 22\u201346.","DOI":"10.1142\/9789812831699_0002"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574050"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0210001"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer\u2010Verlag, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen, Algebraic complexity theory, Annual Reviews, Palo Alto, CA, 1988, 317\u201334791a:68150","DOI":"10.1146\/annurev.cs.03.060188.001533"},{"key":"R14","unstructured":"P. Lancaster and M. Tismenetsky,\n                      The Theory of Matrices\n                      , 2nd ed., Academic Press, 1985."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"R16","unstructured":"J. Matou\u0161ek,\n                      Geometric range searching\n                      , Tech. Report B\u201093\u201009, Free Univ. Berlin, 1993."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69900-9"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/321752.321761"},{"key":"R19","unstructured":"K. Mulmuley,\n                      Computational Geometry: An Introduction Through Randomized Algorithms\n                      , Prentice\u2010Hall, 1994."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Volker Strassen, Algebraic complexity theory, Elsevier, Amsterdam, 1990, 633\u20136721127177","DOI":"10.1016\/B978-0-444-88071-0.50016-3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794275665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:16Z","timestamp":1787335936000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794275665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794275665"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794275665","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}