{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T14:26:25Z","timestamp":1775571985025,"version":"3.50.1"},"reference-count":18,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2001,3,1]],"date-time":"2001-03-01T00:00:00Z","timestamp":983404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4521,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2001,3]]},"DOI":"10.1006\/jcss.2000.1726","type":"journal-article","created":{"date-parts":[[2002,9,18]],"date-time":"2002-09-18T14:19:44Z","timestamp":1032358784000},"page":"267-289","source":"Crossref","is-referenced-by-count":50,"title":["Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes"],"prefix":"10.1006","volume":"62","author":[{"given":"Sam","family":"Buss","sequence":"first","affiliation":[]},{"given":"Dima","family":"Grigoriev","sequence":"additional","affiliation":[]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1006\/jcss.2000.1726_RF1","series-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computation","article-title":"Space complexity in propositional calculus","author":"Alekhnovich","year":"2000"},{"key":"10.1006\/jcss.2000.1726_RF2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1112\/plms\/s3-73.1.1","article-title":"Lower bounds on Hilbert's Nullstellensatz and propositional proofs","volume":"73","author":"Beame","year":"1996","journal-title":"Proc. London Math."},{"key":"10.1006\/jcss.2000.1726_RF3","unstructured":"E. Ben-Sasson, and, R. Impagliazzo, Random CNF's Are Hard for the Polynomial Calculus, unpublished manuscript, 1999."},{"key":"10.1006\/jcss.2000.1726_RF4","series-title":"Homogenization and the Polynomial Calculus","author":"Buresh-Oppenheim","year":"1999"},{"key":"10.1006\/jcss.2000.1726_RF5","series-title":"Proof Complexity and Feasible Arithmetics","first-page":"59","article-title":"Lower bounds on Nullstellensatz proofs via designs","author":"Buss","year":"1998"},{"key":"10.1006\/jcss.2000.1726_RF6","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/BF01294258","article-title":"Proof complexity in algebraic systems and bounded depth Frege systems with modular counting","volume":"6","author":"Buss","year":"1996","journal-title":"Comput. Complexity"},{"key":"10.1006\/jcss.2000.1726_RF7","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1006\/jcss.1998.1585","article-title":"Good degree lower bounds on nullstellensatz refutations of the induction principle","volume":"57","author":"Buss","year":"1998","journal-title":"J. Comput. System Sci."},{"key":"10.1006\/jcss.2000.1726_RF8","doi-asserted-by":"crossref","unstructured":"M. Clegg, J. Edmonds, and R. Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, in Proceedings of the Twenty-eight Annual ACM Symposium on the Theory of Computing, 1996, pp. 174\u2013183.","DOI":"10.1145\/237814.237860"},{"key":"10.1006\/jcss.2000.1726_RF9","series-title":"Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science","article-title":"Nullstellensatz lower bounds for Tseitin tautologies","author":"Grigoriev","year":"1998"},{"key":"10.1006\/jcss.2000.1726_RF10","series-title":"Lower Bounds for Polynomial Calculus Proofs for Binomial Ideals","author":"Grigoriev","year":"1999"},{"key":"10.1006\/jcss.2000.1726_RF11","series-title":"Topics in Algebra","author":"Herstein","year":"1975"},{"key":"10.1006\/jcss.2000.1726_RF12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s000370050024","article-title":"Lower bounds for the polynomial calculus and the Gr\u00f6bner basis algorithm","volume":"8","author":"Impagliazzo","year":"1999","journal-title":"Comput. Complexity"},{"key":"10.1006\/jcss.2000.1726_RF13","unstructured":"J. Kraj\u0131́\u010dek, On the degree of ideal membership proofs from uniform families of polynomials over a finite field, Illinois J. Math, in press."},{"key":"10.1006\/jcss.2000.1726_RF14","series-title":"Mathematical Foundations of Computer Science (MFCS)","article-title":"Lower bounds for a proof system with an exponential speed-up over constant depth Frege systems and over polynomial calculus","volume":"1295","author":"Kraj\u0131́\u010dek","year":"1997"},{"key":"10.1006\/jcss.2000.1726_RF15","series-title":"Descriptive Complexity and Finite Models","first-page":"215","article-title":"Algebraic propositional proof systems","volume":"31","author":"Pitassi","year":"1996"},{"key":"10.1006\/jcss.2000.1726_RF16","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s000370050013","article-title":"Lower bounds for the polynomial calculus","volume":"7","author":"Razborov","year":"1998","journal-title":"Comput. Complexity"},{"key":"10.1006\/jcss.2000.1726_RF17","series-title":"Proceedings of the Nineteenth Annual ACM Symposium on the Theory of Computing","article-title":"Algebraic methods in the theory of lower bounds for Boolean circuit complexity","author":"Smolensky","year":"1987"},{"key":"10.1006\/jcss.2000.1726_RF18","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/7531.8928","article-title":"Hard examples for resolution","volume":"34","author":"Urquhart","year":"1987","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000000917264?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000000917264?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T11:24:31Z","timestamp":1557314671000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000000917264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,3]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,3]]}},"alternative-id":["S0022000000917264"],"URL":"https:\/\/doi.org\/10.1006\/jcss.2000.1726","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2001,3]]}}}