{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:25:25Z","timestamp":1787387125702,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1991,8]]},"abstract":"<jats:p>Let $W \\subseteq R^n $ be scale-invariant and rationally dispersed, i.e., $\\tilde x \\in W$ implies $\\lambda \\tilde x \\in W$ for all real $\\lambda &gt; 0$; and the rationale are dense in both W and $R^n - W$. It is shown that, in the algebraic computation tree model, the problem of deciding whether an input $\\tilde x \\in R^n $ with integer coordinates is a member of W has complexity $\\Omega (\\log _2 \\hat \\beta (W) - 2n)$, where $\\hat \\beta (W)$ is the number of connected components of W that are not of measure 0. This theorem can be used to prove tight lower bounds for the integral-constrained form of many basic problems, such as Element Distinctness, Set Disjointness, Finding Convex Hull, etc. Through further transformations, it leads to lower bounds for problems such as Integer Max Gap and Closest Pair of a simple polygon. The proof involves a nontrivial extension of the Milnor\u2013Thorn techniques for finding upper bounds on the Betti numbers of algebraic varieties.<\/jats:p>","DOI":"10.1137\/0220041","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:34:57Z","timestamp":1109226897000},"page":"655-668","source":"Crossref","is-referenced-by-count":43,"title":["Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains"],"prefix":"10.1137","volume":"20","author":[{"given":"Andrew Chi-Chih","family":"Yao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAERT","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90133-G"},{"key":"RAGSS","unstructured":"A. Aggarwal, L. J. Guibas, J. Saxe, P. Shor,  A linear time algorithm for computing the Voronoi diagram of a convex polygon,  Proc. 19th ACM Symposium on Theory of Computing, New York,  1987,  39\u201345"},{"key":"RAW","unstructured":"A. Aggarwal, J. Wein,  Computational Geometry, Tech. Report, MIT\/LCS\/RSS 3, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA,  1988, Lecture Notes for course 18.409, August"},{"key":"RB","unstructured":"M. Ben-Or,  Lower bounds for algebraic computation trees,  Proc. 15th ACM Symposium on Theory of Computing, Boston, MA,  1983,  80\u201386"},{"key":"RDL","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90026-0"},{"key":"RGY","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90013-5"},{"key":"RJMW","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035829"},{"key":"RLW","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840442"},{"key":"RLR","unstructured":"A. Lubiw, A. Racs,  A lower bound for the integer distinctness problem,  abstract in the French\u2013Israel Conference on Combinatorics, Israel,  1988, November"},{"key":"RMST","unstructured":"Y. Mansour, B. Schieber, P. Tiwari,  Lower bounds for integer greatest common divisor computations,  Proc. 29th IEEE Symposium on Foundations of Computer Science, White Plains, NY,  1988,  54\u201363"},{"key":"RM","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1964-0161339-9"},{"key":"RR","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90141-4"},{"key":"RSE","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90154-8"},{"key":"RSM","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(87)90021-5"},{"key":"RSY","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90002-5"},{"key":"RST","doi-asserted-by":"publisher","DOI":"10.1137\/0212001"},{"key":"RTV","doi-asserted-by":"publisher","DOI":"10.1137\/0217010"},{"key":"RTV","doi-asserted-by":"publisher","DOI":"10.1137\/0217067"},{"key":"RTH","doi-asserted-by":"publisher","DOI":"10.1515\/9781400874842-016"},{"key":"RY","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322342"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0220041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:50:26Z","timestamp":1787338226000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0220041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,8]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,8]]}},"alternative-id":["10.1137\/0220041"],"URL":"https:\/\/doi.org\/10.1137\/0220041","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,8]]}}}