{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T05:23:33Z","timestamp":1737696213838,"version":"3.33.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1007\/bf02770873","type":"journal-article","created":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T09:10:07Z","timestamp":1197623407000},"page":"191-215","source":"Crossref","is-referenced-by-count":4,"title":["Lower bound on testing membership to a polyhedron by algebraic decision and computation trees"],"prefix":"10.1007","volume":"17","author":[{"given":"D.","family":"Grigoriev","sequence":"first","affiliation":[]},{"given":"M.","family":"Karpinski","sequence":"additional","affiliation":[]},{"given":"N.","family":"Vorobjov","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02770873_CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees,Proceedings of ACM Symposium on Theory of Computing, 1983, pp. 80-86.","DOI":"10.1145\/800061.808735"},{"key":"BF02770873_CR2","first-page":"321","volume-title":"Progress in Mathematics","author":"A. Bj\u00f6rner","year":"1994","unstructured":"A. Bj\u00f6rner, Subspace arrangements,Proceedings of 1st European Congress of Mathematics, Paris, 1992, A. Josephet al., eds. Progress in Mathematics, Vol.119, Birkh\u00e4user, Basel, 1994, pp. 321\u2013370."},{"key":"BF02770873_CR3","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rner and L. Lovasz, Linear decision trees, subspace arrangements and M\u00f6bius functions, Preprint, 1992.","DOI":"10.1145\/129712.129730"},{"key":"BF02770873_CR4","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rner, L. Lovasz, and A. Yao, Linear decision trees: Volume estimates and topological bounds,Proceedings of ACM Symposium on Theory of Computing, 1992, pp. 170-177.","DOI":"10.1145\/129712.129730"},{"key":"BF02770873_CR5","volume-title":"On randomized algebraic test complexity, Technical Report TR-92-070","author":"P. Buergisser","year":"1992","unstructured":"P. Buergisser, M. Karpinski, and T. Lickteig, On randomized algebraic test complexity, Technical Report TR-92-070, International Computer Science Institute, Berkeley, CA, 1992."},{"key":"BF02770873_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-71714-7","volume-title":"Stratified Morse Theory","author":"M. Goresky","year":"1988","unstructured":"M. Goresky and R. MacPherson,Stratified Morse Theory, Springer-Verlag, Berlin, 1988."},{"key":"BF02770873_CR7","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigoriev","year":"1988","unstructured":"D. Grigoriev, Complexity of deciding Tarski algebra,J. Symbolic Comput., 5 (1988), 65\u2013108.","journal-title":"J. Symbolic Comput."},{"key":"BF02770873_CR8","series-title":"Computational complexity of sparse real algebraic function interpolation","first-page":"91","volume-title":"Proceedings MEGA \u201992, Progress in Mathematics","author":"D. Grigoriev","year":"1993","unstructured":"D. Grigoriev, M. Karpinski, and M. Singer, Computational complexity of sparse real algebraic function interpolation.Proceedings MEGA \u201992, Progress in Mathematics, Vol.109, Birkh\u00e4user, Basel, 1993, pp. 91\u2013104."},{"key":"BF02770873_CR9","doi-asserted-by":"crossref","unstructured":"D. Grigoriev, M. Karpinski, and N. Vorobjov, Lower bounds on testing membership to a polyhedron by algebraic decision trees,Proceedings of ACM Symposium on Theory of Computing, 1994, pp. 635-644.","DOI":"10.1145\/195058.195418"},{"key":"BF02770873_CR10","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D. Grigoriev","year":"1988","unstructured":"D. Grigoriev and N. Vorobjov, Solving systems of polynomial inequalities in subexponential time,J. Symbolic Comput., 5 (1988), 37\u201364.","journal-title":"J. Symbolic Comput."},{"key":"BF02770873_CR11","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and N. Vorobjov, Counting connected components of a semialgebraic set in subexponential time,Comput. Complexity, 2 (1992), 133-186.","DOI":"10.1007\/BF01202001"},{"key":"BF02770873_CR12","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and N. Vorobjov, Complexity lower bounds for computation trees with elementary transcendental function gates,Proceedings of IEEE Symposium on Foundations of Computer Science, 1994, pp. 48-552. Also inTheoret. Comput. Sci.,157 (1996), 185-214.","DOI":"10.1016\/0304-3975(95)00159-X"},{"key":"BF02770873_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9449-5","volume-title":"Differential Topology","author":"M. Hirsch","year":"1976","unstructured":"M. Hirsch,Differential Topology, Springer-Verlag, New York, 1976."},{"key":"BF02770873_CR14","volume-title":"Algebra","author":"S. Lang","year":"1965","unstructured":"S. Lang,Algebra, Addison-Wesley, Reading, MA, 1965."},{"key":"BF02770873_CR15","first-page":"115","volume-title":"Symbolic and Algebraic Computation","author":"R. Loos","year":"1982","unstructured":"R. Loos, Generalized polynomial remainder sequences, inSymbolic and Algebraic Computation, B. Buchbergeret al., eds., Springer-Verlag, New York, 1982, pp. 115\u2013136."},{"key":"BF02770873_CR16","volume-title":"Convex Polythopes and the Upper Bound Conjecture","author":"P. McMullen","year":"1971","unstructured":"P. McMullen and G. Shephard,Convex Polythopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge, 1971."},{"key":"BF02770873_CR17","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, Fast algorithms for n-dimensional restrictions of hard problems,Proceedings of ACM Symposium on Theory of Computing, 1985, pp. 413-420.","DOI":"10.1145\/22145.22191"},{"key":"BF02770873_CR18","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor, On the Betti numbers of real varieties,Proc. Amer. Math. Soc. 15 (1964), 275\u2013280.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF02770873_CR19","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01613615","volume":"7","author":"J. L. Montana","year":"1996","unstructured":"J. L. Montana, J. E. Morais, and L. M. Pardo, Lower bounds for arithmetic networks, 2: sum of Betti numbers,Appl. Algebra Engrg. Comm. Comput. 7 (1996), 41\u201351.","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"key":"BF02770873_CR20","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF01202285","volume":"4","author":"M.-F. Roy","year":"1994","unstructured":"M.-F. Roy and N. Vorobjov, Finding irreducible components of some real transcendental varieties,Comput. Complexity 4 (1994), 107\u2013132.","journal-title":"Comput. Complexity"},{"key":"BF02770873_CR21","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A. Tarski","year":"1951","unstructured":"A. Tarski,A Decision Method for Elementary Algebra and Geometry, University of California Press, Berkeley, CA, 1951."},{"key":"BF02770873_CR22","volume-title":"Elementary Topics in Differential Geometry","author":"J. A. Thorpe","year":"1977","unstructured":"J. A. Thorpe,Elementary Topics in Differential Geometry, Springer-Verlag, Berlin, 1977."},{"key":"BF02770873_CR23","doi-asserted-by":"crossref","unstructured":"A. Yao, Algebraic decision trees and Euler characteristics,Proceedings of IEEE Symposium on Foundations of Computer Science, 1992, pp. 268-277.","DOI":"10.1109\/SFCS.1992.267765"},{"key":"BF02770873_CR24","doi-asserted-by":"crossref","unstructured":"A. Yao, Decision tree complexity and Betti numbers.Proceedings of ACM Symposium on Theory of Computing, 1994, pp. 615-624.","DOI":"10.1145\/195058.195414"},{"key":"BF02770873_CR25","first-page":"343","volume":"9","author":"A. Yao","year":"1980","unstructured":"A. Yao and R. Rivest, On the polyhedral decision problem,S1AM J. Comput. 9 (1980), 343\u2013347.","journal-title":"S1AM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770873.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02770873\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T18:54:56Z","timestamp":1737658496000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02770873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02770873"],"URL":"https:\/\/doi.org\/10.1007\/bf02770873","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}