{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T22:41:13Z","timestamp":1768776073175,"version":"3.49.0"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814947"],"award-info":[{"award-number":["CCF-1814947"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2220232"],"award-info":[{"award-number":["CCF-2220232"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"DOI":"10.1137\/23m1557593","type":"journal-article","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T07:02:43Z","timestamp":1749538963000},"page":"702-774","source":"Crossref","is-referenced-by-count":1,"title":["The Approximate Degree of DNF and CNF Formulas"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2488-7852","authenticated-orcid":true,"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[{"name":"Department of Computer Science, UCLA, Los Angeles, CA 90095 USA."}]}],"member":"351","published-online":{"date-parts":[[2025,6,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/22.6.583"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a009"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/100792779"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0220-2"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a010"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.003"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/17M1161737"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2021.v017a007"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1595391.1595392"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a010"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0276-2"},{"key":"ref30","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"Minsky M. L.","year":"1969"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1070\/IM2003v067n01ABEH000422"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/080744037"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.2307\/2371291"},{"key":"ref36","first-page":"59","volume":"95","author":"Sherstov A. A.","year":"2008","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a020"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a018"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/2629334"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/120891587"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/15M1015704"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/16M1064477"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/19M1278831"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-021-00211-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T07:02:44Z","timestamp":1749538964000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1557593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/23M1557593"],"URL":"https:\/\/doi.org\/10.1137\/23m1557593","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]}}}