{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T15:35:05Z","timestamp":1747150505847,"version":"3.40.5"},"reference-count":8,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T00:00:00Z","timestamp":1542672000000},"content-version":"am","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"},{"start":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T00:00:00Z","timestamp":1542672000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR\u20101213151"],"award-info":[{"award-number":["CCR\u20101213151"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider tautologies expressing equivalence\u2010chain properties in the spirit of Thapen and Kraj\u00ed\u010dek, which are candidates for exponentially separating depth <jats:italic>k<\/jats:italic> and depth <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/malq201700034-math-0001.png\" xlink:title=\"urn:x-wiley:09425616:media:malq201700034:malq201700034-math-0001\"\/> Frege proof systems. We formulate a special case where the initial member of the equivalence chain is fully specified and the equivalence\u2010chain implications are actually equivalences. This special case is shown to lead to polynomial size resolution refutations. Thus it cannot be used for separating depth <jats:italic>k<\/jats:italic> and depth <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/malq201700034-math-0002.png\" xlink:title=\"urn:x-wiley:09425616:media:malq201700034:malq201700034-math-0002\"\/> propositional systems. We state some H\u00e5stad switching lemma conditions that restrict the possible propositional proofs in more general situations.<\/jats:p>","DOI":"10.1002\/malq.201700034","type":"journal-article","created":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T16:36:01Z","timestamp":1542731761000},"page":"505-513","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Short refutations for an equivalence\u2010chain principle for constant\u2010depth formulas"],"prefix":"10.1002","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3837-334X","authenticated-orcid":false,"given":"Sam","family":"Buss","sequence":"first","affiliation":[{"name":"Department of Mathematics University of California San Diego, 9500 Gilman Dr. La Jolla CA 92093\u20100112 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramyaa","family":"Ramyaa","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering New Mexico Tech 801 Leroy Place Socorro NM 87801 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2018,11,20]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_7_2_1","DOI":"10.1145\/2579822"},{"unstructured":"S. R.Buss Bounded Arithmetic (Bibliopolis 1986) Revision of 1985 Princeton University Ph.D. thesis.","key":"e_1_2_7_3_1"},{"key":"e_1_2_7_4_1","first-page":"143","article-title":"Almost optimal lower bounds for small depth circuits","volume":"5","author":"H\u00e5stad J.","year":"1989","journal-title":"Adv. Comput. Res."},{"doi-asserted-by":"publisher","key":"e_1_2_7_5_1","DOI":"10.1002\/1521-3870(200204)48:3<375::AID-MALQ375>3.0.CO;2-L"},{"volume-title":"Bounded Arithmetic, Propositional Calculus and Complexity Theory, Encyclopedia of Mathematics and its Applications","year":"1995","author":"Kraj\u00ed\u010dek J.","key":"e_1_2_7_6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_7_7_1","DOI":"10.2178\/jsl\/1268917504"},{"volume-title":"Proof Complexity, Encyclopedia of Mathematics and its Applications","year":"2019","author":"Kraj\u00ed\u010dek J.","key":"e_1_2_7_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_7_9_1","DOI":"10.1112\/plms\/pdq044"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201700034","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201700034","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/malq.201700034","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/api.wiley.com\/onlinelibrary\/chorus\/v1\/articles\/10.1002%2Fmalq.201700034","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201700034","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201700034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:54:43Z","timestamp":1694739283000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201700034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,20]]},"references-count":8,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1002\/malq.201700034"],"URL":"https:\/\/doi.org\/10.1002\/malq.201700034","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[2018,11,20]]},"assertion":[{"value":"2017-06-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-28","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}