{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T18:46:40Z","timestamp":1761936400042,"version":"build-2065373602"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1007\/bf01270387","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:42:18Z","timestamp":1111639338000},"page":"357-375","source":"Crossref","is-referenced-by-count":7,"title":["A lower bound for randomized algebraic decision trees"],"prefix":"10.1007","volume":"6","author":[{"given":"Dima","family":"Grigoriev","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]},{"given":"Friedhelm Meyer","family":"auf der Heide","sequence":"additional","affiliation":[]},{"given":"Roman","family":"Smolensky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or,Lower Bounds for Algebraic Computation Trees, Proc. 15th ACM STOC (1983), pp. 80?86.","DOI":"10.1145\/800061.808735"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"C.H. Bennett andJ. Gill,Relative to a Random Oracle A, P A ? NP A ? co-NP A with Probability 1, SIAM J. Comput.10 (1981), pp. 96?113.","journal-title":"SIAM J. Comput."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rner, L. Lov\u00e1sz and A. Yao,Linear Decision Trees: Volume Estimates and Topological Bounds, Proc. 24th ACM STOC (1992), pp. 170?177.","DOI":"10.1145\/129712.129730"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1006\/jcom.1993.1016","volume":"9","author":"P. B\u00fcrgisser","year":"1993","unstructured":"P. B\u00fcrgisser, M. Karpinski andT. Lickteig,On Randomized Algebraic Test Complexity. J. of Complexity9 (1993), pp. 231?251.","journal-title":"J. of Complexity"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D.P. Dobkin","year":"1978","unstructured":"D.P. Dobkin andR.J. Lipton,A Lower Bound of 1\/2n 2 on Linear Search Programms for the Knapsack Problem, J. Compt. Syst. Sci.16 (1978), pp. 413?417.","journal-title":"J. Compt. Syst. Sci."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner,Algorithms in Computational Geometry, Springer, 1987.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"CR7","series-title":"Technical Report TR-93-042","volume-title":"Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees","author":"D. Grigoriev","year":"1993","unstructured":"D. Grigoriev andM. Karpinski,Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees, Technical Report TR-93-042, International Computer Science Institute, Berkeley, 1993."},{"key":"CR8","unstructured":"D. Grigoriev and M. Karpinski,Lower Bound for Randomized Linear Decision Tree Recognizing a Union of Hyperplanes in a Generic Position, Research Report No. 85114-CS, University of Bonn, 1994."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"D. Grigoriev, M. Karpinski, F. Meyer Auf Der Heide and R. Smolensky,A Lower Bound for Randomized Algebraic Decision Trees, Proc. ACM STOC (1996), pp. 612?619.","DOI":"10.1145\/237814.238011"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02770873","volume":"17","author":"D. Grigoriev","year":"1997","unstructured":"D. Grigoriev, M. Karpinski andN. Vorobjov,Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Discrete Comput. Geom. 17 (1997), pp. 191?215.","journal-title":"Discrete Comput. Geom."},{"key":"CR11","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 andN. Vorobjov,Solving Systems of Polynomial Inequalities in Subexponential Time, Journal of Symbolic Comp.5 (1988), pp. 37?64.","journal-title":"Journal of Symbolic Comp."},{"key":"CR12","volume-title":"Algebra","author":"S. Lang","year":"1984","unstructured":"S. Lang,Algebra, Addison-Wesley, New York, 1984."},{"key":"CR13","volume-title":"Convex Polytopes and the Upper Bound Conjecture","author":"P. McMullen","year":"1971","unstructured":"P. McMullen andG. Shephard,Convex Polytopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge (1971)."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1006\/inco.1993.1057","volume":"106","author":"S. Meiser","year":"1993","unstructured":"S. Meiser,Point Location in Arrangements of Hyperplanes, Information and Computation106 (1993), pp. 286?303.","journal-title":"Information and Computation"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer Heide Auf Der","year":"1984","unstructured":"F. Meyer Auf Der Heide,A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, J. ACM31 (1984), pp. 668?676.","journal-title":"J. ACM"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide,Nondeterministic versus Probabilistic Linear Search Algorithms, Proc. IEEE FOCS (1985a), pp. 65?73.","DOI":"10.1109\/SFCS.1985.38"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/4221.4250","volume":"32","author":"F. Meyer Heide auf der","year":"1985","unstructured":"F. Meyer auf der Heide,Lower Bounds for Solving Linear Diophantic Equations on Random Access Machines, J. ACM32 (1985b), pp. 929?937.","journal-title":"J. ACM"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(85)90079-9","volume":"41","author":"F. Meyer Heide auf der","year":"1985","unstructured":"F. Meyer auf der Heide,Simulating Probabilistic by Deterministic Algebraic Computation Trees, Theoretical Computer Science41 (1985c), pp. 325?330.","journal-title":"Theoretical Computer Science"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/3828.3838","volume":"32","author":"U. Manber","year":"1985","unstructured":"U. Manber andM. Tompa,Probabilistic, Nondeterministic and Alternating Decision Trees, J. ACM, Vol. 32 (1985), pp. 720?732.","journal-title":"J. ACM"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"M. Snir,Lower Bounds for Probabilistic Linear Decision Trees, Theor. Comput. Sci., Vol. 38 (1985), pp. 69?82.","journal-title":"Theor. Comput. Sci."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J. M. Steele","year":"1982","unstructured":"J. M. Steele andA. C. Yao,Lower Bounds for Algebraic Decision Trees, J. of Algorithms3 (1982), pp. 1?8.","journal-title":"J. of Algorithms"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"A. Tarski,A Decision Method for Elementary Algebra and Geometry, University of California Press, 1951.","DOI":"10.1525\/9780520348097"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1145\/322276.322289","volume":"28","author":"A. Yao","year":"1981","unstructured":"A. Yao,A Lower Bound to Finding Convex Hulls, J. ACM28 (1981), pp. 780?787.","journal-title":"J. ACM"},{"key":"CR24","unstructured":"A. Yao,Algebraic Decision Trees and Euler Characteristics, Proc. 33rd IEEE FOCS (1992), pp. 268?277."},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"A. Yao,Decision Tree Complexity and Betti Numbers, Proc. 26th ACM STOC (1994), pp. 615?624.","DOI":"10.1145\/195058.195414"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270387.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01270387\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T09:13:04Z","timestamp":1735377184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01270387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF01270387"],"URL":"https:\/\/doi.org\/10.1007\/bf01270387","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}