{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T20:10:02Z","timestamp":1737576602280,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664123"},{"type":"electronic","value":"9783540483212"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48321-7_1","type":"book-chapter","created":{"date-parts":[[2007,11,5]],"date-time":"2007-11-05T12:57:55Z","timestamp":1194267475000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized complexity of linear arrangements and polyhedra?"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"1_CR1","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"1_CR2","unstructured":"M. Ben-Or, Lower Bounds for Algebraic Computation Trees, Proc. 15th ACM STOC (1983), pp. 80\u201386."},{"key":"1_CR3","unstructured":"A. Bj\u00f6rner, L. Lov\u2019asz and A. Yao, Linear Decision Trees: Volume Estimates and Topological Bounds, Proc. 24th ACM STOC (1992), pp. 170\u2013177."},{"key":"1_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-57568-5_251","volume-title":"Proc. ISAAC\u201993","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, Time Space Tradeoffs (Getting Closer to the Barrier?), Proc. ISAAC\u201993, LNCS 762 (1993), Springer, 1993, pp. 209\u2013220."},{"key":"1_CR5","unstructured":"A. Borodin, R. Ostrovsky and Y. Rabani, Lower Bounds for High Dimensional Nearest Neighbour Search and Related Problems, Proc. 31st ACM STOC (1999), pp. 312\u2013321."},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1006\/jcom.1993.1016","volume":"9","author":"P. B\u00fcrgisser","year":"1993","unstructured":"P. B\u00fcrgisser, M. Karpinski and T. Lickteig, On Randomized Algebraic Test Complexity, J. of Complexity 9 (1993), pp. 231\u2013251.","journal-title":"J. of Complexity"},{"key":"1_CR7","unstructured":"F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, K. Werther, On Real Turing Machines that Toss Coins, Proc. 27th ACM STOC (1995), pp. 335\u2013342."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D.P. Dobkin","year":"1978","unstructured":"D.P. Dobkin and R. J. Lipton, A Lower Bound of 1\/2n 2 on Linear Search Programs for the Knapsack Problem, J. Compt. Syst. Sci. 16 (1978), pp. 413\u2013417.","journal-title":"J. Compt. Syst. Sci."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, Algorithms in Computational Geometry, Springer, 1987.","DOI":"10.1007\/978-3-642-61568-9"},{"key":"1_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/3-540-60084-1_73","volume-title":"Proc. 22nd ICALP\u201995","author":"R. Freivalds","year":"1995","unstructured":"R. Freivalds and M. Karpinski, Lower Time Bounds for Randomized Computation, Proc. 22nd ICALP\u201995, LNCS 944, Springer, 1995, pp. 183\u2013195."},{"key":"1_CR11","unstructured":"B. Gr\u00fcnbaum, Convex Polytopes, John Wiley, 1967."},{"key":"1_CR12","volume-title":"Technical Report TR-93-042","author":"D. Grigoriev","year":"1993","unstructured":"D. Grigoriev and M. 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":"1_CR13","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":"1_CR14","unstructured":"D. Grigoriev and M. Karpinski, Randomized \u03bc(n2) Lower Bound for Knapsack, Proc. 29th ACM STOC (1997), pp. 76\u201385."},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF01270387","volume":"6","author":"D. Grigoriev","year":"1997","unstructured":"D. Grigoriev, M. Karpinski, F. Meyer auf der Heide and R. Smolensky, A Lower Bound for Randomized Algebraic Decision Trees, Comput. Complexity 6 (1997), pp. 357\u2013375.","journal-title":"Comput. Complexity"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01270388","volume":"6","author":"D. Grigoriev","year":"1997","unstructured":"D. Grigoriev, M. Karpinski, and R. Smolensky, Randomization and the Computational Power of Analytic and Algebraic Decision Trees, Comput. Complexity 6 (1997), pp. 376\u2013388.","journal-title":"Comput. Complexity"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF02770873","volume":"17","author":"D. Grigoriev","year":"1997","unstructured":"D. Grigoriev, M. Karpinski and N. Vorobjov, Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Discrete Comput. Geom. 17 (1997), pp. 191\u2013215.","journal-title":"Discrete Comput. Geom."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s000370050010","volume":"7","author":"D. Grigoriev","year":"1998","unstructured":"D. Grigoriev, M. Karpinski and A. C. Yao, An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX, Computational Complexity 7 (1998), pp. 193\u2013203.","journal-title":"Computational Complexity"},{"key":"1_CR19","unstructured":"D. Grigoriev, Randomized Complexity Lower Bounds, Proc. 30th ACM STOC (1998), pp. 219\u2013223."},{"key":"1_CR20","unstructured":"M. Karpinski, On the Computational Power of Randomized Branching Programs, Proc. Randomized Algorithms 1998, Brno, 1998, pp. 1\u201312."},{"key":"1_CR21","unstructured":"M. Karpinski, Randomized OBDDs and the Model Checking, Proc. Probabilistic Methods in Verification, PROBMIV\u201998, Indianapolis, 1998, pp. 35\u201338."},{"key":"1_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/BFb0029630","volume-title":"Proc. MFCS\u201990","author":"M. Karpinski","year":"1990","unstructured":"M. Karpinski and F. Meyer auf der Heide, On the Complexity of Genuinely Polynomial Computation, Proc. MFCS\u201990, LNCS 452, Springer, 1990, pp. 362\u2013368."},{"key":"1_CR23","series-title":"Lect Notes Comput Sci","first-page":"189","volume-title":"Randomness, Provability, and the Separation of Monte Carlo Time and Space","author":"M. Karpinski","year":"1988","unstructured":"M. Karpinski and R. Verbeek, Randomness, Provability, and the Separation of Monte Carlo Time and Space, LNCS 270 (1988), Springer, 1988, pp. 189\u2013207."},{"key":"1_CR24","volume-title":"Algebra","author":"S. Lang","year":"1984","unstructured":"S. Lang, Algebra, Addison-Wesley, New York, 1984."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/3828.3838","volume":"32","author":"U. Manber","year":"1985","unstructured":"U. Manber and M. Tompa, Probabilistic, Nondeterministic and Alternating Decision Trees, J. ACM 32 (1985), pp. 720\u2013732.","journal-title":"J. ACM"},{"key":"1_CR26","doi-asserted-by":"publisher","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 Computation 106 (1993), pp. 286\u2013303.","journal-title":"Information and Computation"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. M. Heide auf der","year":"1984","unstructured":"F. Meyer auf der Heide, A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, J. ACM 31 (1984), pp. 668\u2013676.","journal-title":"J. ACM"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, Nondeterministic versus Probabilistic Linear Search Algorithms, Proc. IEEE FOCS (1985a), pp. 65\u201373.","DOI":"10.1109\/SFCS.1985.38"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/4221.4250","volume":"32","author":"F. M. Heide auf der","year":"1985","unstructured":"F. Meyer auf der Heide, Lower Bounds for Solving Linear Diophantine Equations on Random Access Machines, J. ACM 32 (1985), pp. 929\u2013937.","journal-title":"J. ACM"},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(85)90079-9","volume":"41","author":"F. M. Heide auf der","year":"1985","unstructured":"F. Meyer auf der Heide, Simulating Probabilistic by Deterministic Algebraic Computation Trees, Theoretical Computer Science 41 (1985c), pp. 325\u2013330.","journal-title":"Theoretical Computer Science"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"275","DOI":"10.2307\/2034050","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor, On the Betti Numbers of Real Varieties, Proc. Amer. Math. Soc. 15 (1964), pp. 275\u2013280.","journal-title":"Proc. Amer. Math. Soc."},{"key":"1_CR32","unstructured":"M.O. Rabin, Proving Simultaneous Positivity of Linear Forms, J. Comput. Syst. Sciences 6 (1972), pp. 639\u2013650."},{"key":"1_CR33","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Proc. FCT\u201991","author":"A. Razborov","year":"1991","unstructured":"A. Razborov, Lower Bounds for Deterministic and Nondeterministic Branching Programs, Proc. FCT\u201991, LNCS 529, Springer, 1991, pp. 47\u201360."},{"key":"1_CR34","unstructured":"J. Simon and W.J. Paul, Decision Trees and Random Access Machines, L\u2019Enseignement Mathematique. Logic et Algorithmic, Univ. Geneva, 1982, pp. 331\u2013340."},{"key":"1_CR35","doi-asserted-by":"publisher","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. 38 (1985), pp. 69\u201382.","journal-title":"Theor. Comput. Sci."},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J.M. Steele","year":"1982","unstructured":"J.M. Steele and A.C. Yao, Lower Bounds for Algebraic Decision Trees, J. of Algorithms 3 (1982), pp. 1\u20138.","journal-title":"J. of Algorithms"},{"key":"1_CR37","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":"1_CR38","unstructured":"J. S. Thathachar, On Separating the Read-k-Times Branching Program Hierarchy, Proc. 30th ACM STOC (1998), pp. 653\u2013662."},{"key":"1_CR39","volume-title":"Sur L\u2019Homologie des Vari\u00e8et\u00e8s Alg\u00e8briques R\u00e8elles","author":"R. Thom","year":"1965","unstructured":"R. Thom, Sur L\u2019Homologie des Vari\u00e8et\u00e8s Alg\u00e8briques R\u00e8elles, Princeton University Press, Princeton, 1965."},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(94)90052-3","volume":"49","author":"H.F. Ting","year":"1994","unstructured":"H.F. Ting and A.C. Yao, Randomized Algorithm for finding Maximum with O((log n)2) Polynomial Tests, Information Processing Letters 49 (1994), pp. 39\u201343.","journal-title":"Information Processing Letters"},{"key":"1_CR41","unstructured":"A. Wigderson and A.C. Yao, A Lower Bound for Finding Minimum on Probabilistic Decision Trees, to appear."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1145\/322276.322289","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"A.C. Yao, A Lower Bound to Finding Convex Hulls, J. ACM 28 (1981), pp. 780\u2013787.","journal-title":"J. ACM"},{"key":"1_CR43","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0304-3975(82)90060-3","volume":"19","author":"A.C. Yao","year":"1982","unstructured":"A.C. Yao, On the Time-Space Tradeoff for Sorting with Linear Queries, Theoretical Computer Science 19 (1982), pp. 203\u2013218.","journal-title":"Theoretical Computer Science"},{"key":"1_CR44","unstructured":"A.C. Yao, Algebraic Decision Trees and Euler Characteristics, Proc. 33rd IEEE FOCS (1992), pp. 268\u2013277."},{"key":"1_CR45","unstructured":"A.C. Yao, Decision Tree Complexity and Betti Numbers, Proc. 26th ACM STOC (1994), pp. 615\u2013624."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48321-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T03:15:27Z","timestamp":1737515727000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48321-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664123","9783540483212"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-48321-7_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"3 June 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}