{"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":1787387125869,"version":"build-2736575974"},"reference-count":11,"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":[[1980,5]]},"abstract":"<jats:p>Computational problems sometimes can be cast in the following form: Given a point ${\\bf x}$ in $R^n $, determine if ${\\bf x}$ lies in some fixed polyhedron. In this paper we give a general lower bound to the complexity of such problems, showing that $\\frac{1}{2}\\log _2 f_s $ linear comparisons are needed in the worst case, for any polyhedron with $f_s$s-dimensional faces. For polyhedra with abundant faces, this leads to lower bounds nonlinear in n, the number of variables.<\/jats:p>","DOI":"10.1137\/0209028","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:21:58Z","timestamp":1109226118000},"page":"343-347","source":"Crossref","is-referenced-by-count":31,"title":["On the Polyhedral Decision Problem"],"prefix":"10.1137","volume":"9","author":[{"given":"Andrew C.","family":"Yao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald L.","family":"Rivest","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","unstructured":"D. P. Dobkin, R. J. Lipton, S. P. Reiss,  Excursions into geometry, Computer Science Dept. Tech. Rep., 71, Yale University, New Haven, CT,  1976"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322206"},{"key":"R3","volume-title":"Convex polytopes","author":"Gr\u00fcnbaum Branko","year":"1967"},{"key":"R4","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(72)80034-5"},{"key":"R6","volume-title":"Modern Algebra and Matrix Theory","author":"Schreier O.","year":"1959"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1975542135"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46216-0"},{"key":"R9","unstructured":"R. E. Tarjan,  Applications of path compressions on balanced trees, Computer Science Dept. Rep., STAN-CS-75-512, Stanford University, Stanford, CA,  1975"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.20"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Andrew C. Yao, David M. Avis, Ronald L. Rivest,  An  \u03a9(n2logn) lower bound to the shortest paths problem,  Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York,  1977,  11\u201317 58:19363","DOI":"10.1145\/800105.803391"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0209028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:32Z","timestamp":1787337152000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0209028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980,5]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1980,5]]}},"alternative-id":["10.1137\/0209028"],"URL":"https:\/\/doi.org\/10.1137\/0209028","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1980,5]]}}}