{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T07:30:23Z","timestamp":1749540623630},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1137\/17m1161737","type":"journal-article","created":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T13:06:41Z","timestamp":1571922401000},"page":"FOCS17-59-FOCS17-96","source":"Crossref","is-referenced-by-count":4,"title":["A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$"],"prefix":"10.1137","volume":"49","author":[{"given":"Mark","family":"Bun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2019,10,22]]},"reference":[{"key":"atypb1","first-page":"3","author":"Aaronson S.","year":"2008","journal-title":"PA"},{"key":"atypb2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.26421\/QIC12.1-2-3","volume":"12","author":"Aaronson S.","year":"2012","journal-title":"Quantum Inform. Comput."},{"key":"atypb3","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1145\/2897518.2897644","volume":"2016","author":"Aaronson S.","year":"2016","journal-title":"STOC"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a003"},{"key":"atypb6","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/2897518.2897524","volume":"2016","author":"Ambainis A.","year":"2016","journal-title":"STOC"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/080712167"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/100792779"},{"key":"atypb13","doi-asserted-by":"crossref","first-page":"670","DOI":"10.26421\/QIC12.7-8-11","volume":"12","author":"Beame P.","year":"2012","journal-title":"Quantum Inform. Comput."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263422"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_21"},{"key":"atypb18","first-page":"24","author":"Buhrman H.","year":"2007","journal-title":"IEEE Computer Society"},{"key":"atypb19","first-page":"297","volume":"2018","author":"Bun M.","year":"2018","journal-title":"STOC"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_26"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a016"},{"key":"atypb26","first-page":"387","author":"Chandrasekaran K.","year":"2014","journal-title":"ACM"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_30"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1595391.1595392"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a010"},{"key":"atypb36","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/3-540-45061-0_25","volume":"2719","author":"P. H\u00f8","year":"2003","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271266"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"atypb41","first-page":"587","volume":"7","author":"Klivans A. R.","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0276-2"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2173-3"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/080744037"},{"key":"atypb54","first-page":"59","volume":"95","author":"Sherstov A. A.","year":"2008","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0274-4"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/08071421X"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a020"},{"key":"atypb60","first-page":"921","author":"Sherstov A. A.","year":"2013","journal-title":"ACM"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a018"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2759-7"},{"key":"atypb65","first-page":"431","author":"Sherstov A. A.","year":"2015","journal-title":"IEEE"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188958"},{"key":"atypb68","doi-asserted-by":"crossref","first-page":"444","DOI":"10.26421\/QIC9.5-6-7","volume":"9","author":"Shi Y.","year":"2009","journal-title":"Quantum Inform. Comput."},{"key":"atypb71","first-page":"551","author":"Tal A.","year":"2014","journal-title":"PA"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"atypb74","first-page":"1","author":"Thaler J.","year":"2016","journal-title":"Italy"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_68"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1161737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T13:48:23Z","timestamp":1664718503000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1161737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,22]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/17M1161737"],"URL":"https:\/\/doi.org\/10.1137\/17m1161737","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,22]]}}}