{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T23:44:16Z","timestamp":1771890256660,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T00:00:00Z","timestamp":1503964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1319788 and CCF-1420349"],"award-info":[{"award-number":["CCF-1319788 and CCF-1420349"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every\n            <jats:italic>d<\/jats:italic>\n            \u2265 2, there is an explicit\n            <jats:italic>n<\/jats:italic>\n            -variable Boolean function\n            <jats:italic>f<\/jats:italic>\n            , computed by a linear-size depth-\n            <jats:italic>d<\/jats:italic>\n            formula, which is such that any depth-(\n            <jats:italic>d<\/jats:italic>\n            \u22121) circuit that agrees with\n            <jats:italic>f<\/jats:italic>\n            on (1\/2 +\n            <jats:italic>o<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            (1)) fraction of all inputs must have size exp(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03a9 (1\/d)<\/jats:sup>\n            ). This answers an open question posed by H\u00e5stad in his Ph.D. thesis (H\u00e5stad 1986b).\n          <\/jats:p>\n          <jats:p>Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of H\u00e5stad (1986a), Cai (1986), and Babai (1987). We also use our result to show that there is no \u201capproximate converse\u201d to the results of Linial, Mansour, Nisan (Linial et al. 1993) and (Boppana 1997) on the total influence of bounded-depth circuits.<\/jats:p>\n          <jats:p>\n            A key ingredient in our proof is a notion of\n            <jats:italic>random projections<\/jats:italic>\n            which generalize random restrictions.\n          <\/jats:p>","DOI":"10.1145\/3095799","type":"journal-article","created":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T17:49:18Z","timestamp":1504028958000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["An Average-Case Depth Hierarchy Theorem for Boolean Circuits"],"prefix":"10.1145","volume":"64","author":[{"given":"Johan","family":"H\u00e5stad","sequence":"first","affiliation":[{"name":"KTH Stockholm, Stockholm, Sweden"}]},{"given":"Benjamin","family":"Rossman","sequence":"additional","affiliation":[{"name":"University of Toronto, Ontario, Canada"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, U.S.A"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, IL, U.S.A"}]}],"member":"320","published-online":{"date-parts":[[2017,8,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Scott Aaronson. The Complexity Zoo. Retrieved from http:\/\/cse.unl.edu\/&sim;cbourke\/latex\/ComplexityZoo.pdf.  Scott Aaronson. The Complexity Zoo. Retrieved from http:\/\/cse.unl.edu\/&sim;cbourke\/latex\/ComplexityZoo.pdf."},{"key":"e_1_2_1_2_1","volume-title":"Electr. Colloq. Comput. Complex. 17","author":"Aaronson Scott","year":"2010","unstructured":"Scott Aaronson . 2010 a. A counterexample to the generalized linial-nisan conjecture . Electr. Colloq. Comput. Complex. 17 (2010), 109. Scott Aaronson. 2010a. A counterexample to the generalized linial-nisan conjecture. Electr. Colloq. Comput. Complex. 17 (2010), 109."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.17"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195207"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90036-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90043-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/070691954"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 27th Conference on Computational Complexity. 117--125","author":"Beame Paul","year":"2012","unstructured":"Paul Beame , Russell Impagliazzo , and Srikanth Srinivasan . 2012 . Approximating by small height decision trees and a deterministic algorithm for - . In Proceedings of the 27th Conference on Computational Complexity. 117--125 . Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. 2012. Approximating by small height decision trees and a deterministic algorithm for -. In Proceedings of the 27th Conference on Computational Complexity. 117--125."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00157-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00131-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234564"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12133"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/279082.279085"},{"key":"e_1_2_1_20_1","volume-title":"Theory of Computational Complexity","author":"Du Ding-Zhu","unstructured":"Ding-Zhu Du and Ker- I Ko. 2000. Theory of Computational Complexity . John Wiley 8 Sons, Inc. Ding-Zhu Du and Ker-I Ko. 2000. Theory of Computational Complexity. John Wiley 8 Sons, Inc."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00034-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.35"},{"key":"e_1_2_1_23_1","volume-title":"On the size of depth-three boolean circuits for computing multilinear functions. Electronic Colloquium on Computational Complexity","author":"Goldreich Oded","year":"2013","unstructured":"Oded Goldreich and Avi Wigderson . 2013. On the size of depth-three boolean circuits for computing multilinear functions. Electronic Colloquium on Computational Complexity ( 2013 ). Oded Goldreich and Avi Wigderson. 2013. On the size of depth-three boolean circuits for computing multilinear functions. Electronic Colloquium on Computational Complexity (2013)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/171479.171481"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_2_1_26_1","volume-title":"Computational Limitations for Small Depth Circuits","author":"H\u00e5stad Johan","unstructured":"Johan H\u00e5stad . 1986b. Computational Limitations for Small Depth Circuits . MIT Press , Cambridge, MA . Johan H\u00e5stad. 1986b. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_27_1","volume-title":"Almost Optimal Lower Bounds for Small Depth Circuits","author":"H\u00e5stad Johan","unstructured":"Johan H\u00e5stad . 1989. Almost Optimal Lower Bounds for Small Depth Circuits . JAI Press , 143--170. Johan H\u00e5stad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. JAI Press, 143--170."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/120897432"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.18"},{"key":"e_1_2_1_30_1","unstructured":"Hamed Hatami. 2014. Scribe notes for the course COMP760: Harmonic Analysis of Boolean Functions. Retrieved from http:\/\/cs.mcgill.ca\/&sim;hatami\/comp760-2014\/lectures.pdf.  Hamed Hatami. 2014. Scribe notes for the course COMP760: Harmonic Analysis of Boolean Functions. Retrieved from http:\/\/cs.mcgill.ca\/&sim;hatami\/comp760-2014\/lectures.pdf."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/181462.181463"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/219817.219822"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.77"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959894"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90011-8"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808717"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1043"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375474"},{"key":"e_1_2_1_43_1","unstructured":"Ryan O\u2019Donnell. 2007. Lecture 29: Open Problems. Scribe notes for the course CMU 18-859S: Analysis of Boolean Functions. Retrieved from http:\/\/www.cs.cmu.edu\/&sim;odonnell\/boolean-analysis.  Ryan O\u2019Donnell. 2007. Lecture 29: Open Problems. Scribe notes for the course CMU 18-859S: Analysis of Boolean Functions. Retrieved from http:\/\/www.cs.cmu.edu\/&sim;odonnell\/boolean-analysis."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_19"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490273"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.33"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852052"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.67"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703428555"},{"key":"e_1_2_1_52_1","volume-title":"Handbook of Combinatorics","author":"Shmoys David","unstructured":"David Shmoys and \u00c9va Tardos . 1995. Computational complexity . In Handbook of Combinatorics (Ronald Graham, Martin Gr\u00f6tschel, and L\u00e1szlo Lov\u00e1sz, eds.), Vol. 2 . North-Holland . David Shmoys and \u00c9va Tardos. 1995. Computational complexity. In Handbook of Combinatorics (Ronald Graham, Martin Gr\u00f6tschel, and L\u00e1szlo Lov\u00e1sz, eds.), Vol. 2. North-Holland."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808733"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_55_1","first-page":"553","article-title":"Realizations of linear functions by formulas using V, 8","volume":"136","author":"Subbotovskaya Bella","year":"1961","unstructured":"Bella Subbotovskaya . 1961 . Realizations of linear functions by formulas using V, 8 , . Dokl. Akad. Nauk SSSR 136 , 3 (1961), 553 -- 555 . Bella Subbotovskaya. 1961. Realizations of linear functions by formulas using V, 8, . Dokl. Akad. Nauk SSSR 136, 3 (1961), 553--555.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_56_1","volume-title":"Query complexity, or why is it difficult to separate NPA &cap","author":"Tardos G\u00e1bor","year":"1989","unstructured":"G\u00e1bor Tardos . 1989. Query complexity, or why is it difficult to separate NPA &cap ; coNPA from PA by random oracles A ?Combinatorica 9, 4 ( 1989 ), 385--392. G\u00e1bor Tardos. 1989. Query complexity, or why is it difficult to separate NPA &cap; coNPA from PA by random oracles A?Combinatorica 9, 4 (1989), 385--392."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808739"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3061640.3061648"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-3394-4_14"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 34th Foundations of Software Technology and Theoretical Computer Science Conference.","author":"Williams Ryan","year":"2014","unstructured":"Ryan Williams . 2014 b. The polynomial method in circuit complexity applied to algorithm design (invited survey) . In Proceedings of the 34th Foundations of Software Technology and Theoretical Computer Science Conference. Ryan Williams. 2014b. The polynomial method in circuit complexity applied to algorithm design (invited survey). In Proceedings of the 34th Foundations of Software Technology and Theoretical Computer Science Conference."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3095799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3095799","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3095799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:53Z","timestamp":1750217813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3095799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,29]]},"references-count":62,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3095799"],"URL":"https:\/\/doi.org\/10.1145\/3095799","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,29]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}