{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:16Z","timestamp":1725460036283},"publisher-location":"Boston","reference-count":36,"publisher":"Kluwer Academic Publishers","isbn-type":[{"type":"print","value":"1402081405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/1-4020-8141-3_10","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T15:15:11Z","timestamp":1140534911000},"page":"97-110","source":"Crossref","is-referenced-by-count":0,"title":["Degree Bounds on Polynomials and Relativization Theory"],"prefix":"10.1007","author":[{"given":"Holger","family":"Spakowski","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Tripathi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon and R. Beigel. Lower bounds for approximations by low degree polynomials over Z m In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, pages 184\u2013187, Los Alamitos, CA, June 18\u201321 2000. IEEE Computer Society.","DOI":"10.1109\/CCC.2001.933885"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"V. Arvind and P. Kurur. Graph isomorphism is in SPP. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pages 743\u2013750, Los Alamitos, November 16\u201319 2002. IEEE Computer Society.","DOI":"10.1109\/SFCS.2002.1181999"},{"issue":"5","key":"10_CR3","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0020-0190(86)90078-5","volume":"23","author":"K. Ambos-Spies","year":"1986","unstructured":"K. Ambos-Spies. A note on complete problems for complexity classes. Information Processing Letters, 23(5):227\u2013230, 1986.","journal-title":"Information Processing Letters"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48, 2001.","DOI":"10.1145\/502090.502097"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In Proceedings of the 30th ACM Symposium on Theory of Computing, pages 203\u2013208. ACM Press, May 1998.","DOI":"10.1145\/276698.276737"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"R. Beigel. The polynomial method in circuit complexity. In Proceedings of the 8th Structure in Complexity Theory Conference, pages 82\u201395, San Diego, CA, USA, May 1993. IEEE Computer Society Press.","DOI":"10.1109\/SCT.1993.336538"},{"issue":"4","key":"10_CR7","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01263422","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel. Perceptrons, PP, and the polynomial hierarchy. Computational Complexity, 4(4):339\u2013349, 1994.","journal-title":"Computational Complexity"},{"issue":"2","key":"10_CR8","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R. Beigel","year":"1995","unstructured":"R. Beigel, N. Reingold, and D. Spielman. PP is closed under intersection. Journal of Computer and System Sciences, 50(2):191\u2013202, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR9","unstructured":"M. de Graaf and P. Valiant. Comparing EQP and MODp k P using polynomial degree lower bounds. Technical Report quant-ph\/0211179, Quantum Physics, 2002."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01111276","volume":"86","author":"H. Ehlich","year":"1964","unstructured":"H. Ehlich and K. Zeller. Schwankung von Polynomen zwischen Gitterpunkten. Mathematische Zeitschrift, 86:41\u201344, 1964.","journal-title":"Mathematische Zeitschrift"},{"issue":"2","key":"10_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00224-002-1089-8","volume":"36","author":"S. Fenner","year":"2003","unstructured":"S. Fenner. PP-lowness and a simple definition of AWPP. Theory of Computing Systems, 36(2):199\u2013212, 2003.","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"10_CR12","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"10_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0890-5401(03)00018-X","volume":"182","author":"S. Fenner","year":"2003","unstructured":"S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder\u2019s toolkit. Information and Computation, 182(2):95\u2013136, 2003.","journal-title":"Information and Computation"},{"issue":"2","key":"10_CR14","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1006\/jcss.1999.1651","volume":"59","author":"L. Fortnow","year":"1999","unstructured":"L. Fortnow and J. Rogers. Complexity limitations on quantum computation. Journal of Computer and System Sciences, 59(2):240\u2013252, 1999.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0304-3975(94)90251-8","volume":"134","author":"L. Fortnow","year":"1994","unstructured":"L. Fortnow, J. Rompel, and M. Sipser. On the power of multi-prover interactive protocols. Theoretical Computer Science, 134:545\u2013557, 1994.","journal-title":"Theoretical Computer Science"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"S. Gupta. The power of witness reduction. In Proceedings of the 6th Structure in Complexity Theory Conference, pages 43\u201359. IEEE Computer Society Press, June\/July 1991.","DOI":"10.1109\/SCT.1991.160242"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J. Hartmanis","year":"1988","unstructured":"J. Hartmanis and L. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science, 58:129\u2013142, 1988.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"10_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1142\/S012905419300016X","volume":"4","author":"L. Hemaspaandra","year":"1993","unstructured":"L. Hemaspaandra, S. Jain, and N. Vereshchagin. Banishing robust Turing completeness. International Journal of Foundations of Computer Science, 4(3):245\u2013265, 1993.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"4","key":"10_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/219817.219822","volume":"26","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra, A. Ramachandran, and M. Zimand. Worlds to die for. SIGACT News, 26(4):5\u201315, 1995.","journal-title":"SIGACT News"},{"key":"10_CR20","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"M. Minsky","year":"1988","unstructured":"M. Minsky and S. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Massachusetts, expanded edition, 1988. First edition appeared in 1968.","edition":"expanded editio"},{"issue":"4","key":"10_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and M. Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4(4):301\u2013313, 1994.","journal-title":"Computational Complexity"},{"issue":"3","key":"10_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"M. Ogiwara and L. Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Sciences, 46(3):295\u2013325, 1993.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"10_CR23","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/0703024","volume":"3","author":"T. J. Rivlin","year":"1966","unstructured":"T. J. Rivlin and E. W. Cheney. A comparison of uniform approximations on an interval and a finite subset thereof. SIAM Journal on Numerical Analysis, 3(2):311\u2013320, June 1966.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"K. Regan. Polynomials and combinatorial definitions of languages. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 261\u2013293. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_11"},{"key":"10_CR25","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J. Rosser","year":"1962","unstructured":"J. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6:64\u201394, 1962.","journal-title":"Illinois Journal of Mathematics"},{"key":"10_CR26","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning. A low and a high hierarchy within NP. Journal of Computer and System Sciences, 27:14\u201328, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"M. Sipser. On relativization and the existence of complete sets. In Proceedings of the 9th International Colloquium on Automata, Languages, and Programming, pages 523\u2013531. Springer-Verlag Lecture Notes in Computer Science #140, 1982.","DOI":"10.1007\/BFb0012797"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 77\u201382. ACM Press, May 1987.","DOI":"10.1145\/28395.28404"},{"key":"10_CR29","unstructured":"H. Spakowski and R. Tripathi. Degree bounds on polynomials and relativization theory. Technical Report TR820, Department of Computer Science, University of Rochester, November 2003."},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"H. Spakowski, M. Thakur, and R. Tripathi. Quantum and classical complexity classes: Separations, collapses, and closure properties. In Proceedings of the 23rd Conference on FSTTCS, pages 375\u2013386. Springer-Verlag Lecture Notes in Computer Science #2914, December 2003.","DOI":"10.1007\/978-3-540-24597-1_32"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"J. Tarui. Degree complexity of boolean functions and its applications to relativized separations. In Proceedings of the 6th Annual Conference on Structure in Complexity Theory (SCTC\u2019 91), pages 285\u2013285, Chicago, IL, USA, June 1991. IEEE Computer Society Press.","DOI":"10.1109\/SCT.1991.160282"},{"issue":"2","key":"10_CR32","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 21(2):316\u2013328, 1992.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"10_CR33","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865\u2013877, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"10_CR34","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/116825.116858","volume":"38","author":"J. Tor\u00e1n","year":"1991","unstructured":"J. Tor\u00e1n. Complexity classes defined by counting quantifiers. Journal of the ACM, 38(3):753\u2013774, 1991.","journal-title":"Journal of the ACM"},{"issue":"2","key":"10_CR35","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1070\/IM1994v042n02ABEH001537","volume":"42","author":"N. Vereshchagin","year":"1994","unstructured":"N. Vereshchagin, Relativizable and nonrelativizable theorems in the polynomial theory of algorithms. Russian Academy of Sciences-Izvestiya-Mathematics, 42(2):261\u2013298, 1994.","journal-title":"Russian Academy of Sciences-Izvestiya-Mathematics"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Nikolai K. Vereshchagin. Relativizability in complexity theory. In L.D. Beklemishev, M. Pentus, and N. Vereshchagin, Provability, Complexity, Grammars, volume 192 of 2, pages 87\u2013172. AMS Translations, 1999.","DOI":"10.1090\/trans2\/192\/03"}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:28:06Z","timestamp":1619555286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["1402081405"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_10","relation":{},"subject":[]}}