{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T20:26:42Z","timestamp":1779222402579,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,12,1]],"date-time":"2015-12-01T00:00:00Z","timestamp":1448928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>We give an overview of a recent result [RST15] showing that the polynomial hierarchy is in finite relative to a random oracle. Since the early 1980s it has been known that this result would follow from a certain \"average-case depth hierarchy theorem\" for Boolean circuits. In this article we present some background and history of related relativized separations; sketch the argument showing how the polynomial hierarchy result follows from the circuit lower bound; and explain the techniques underlying the new circuit lower bound.<\/jats:p>","DOI":"10.1145\/2852040.2852052","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"50-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Complexity Theory Column 89"],"prefix":"10.1145","volume":"46","author":[{"given":"Benjamin","family":"Rossman","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago"}]}],"member":"320","published-online":{"date-parts":[[2015,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Scott Aaronson. The Complexity Zoo. Available at http:\/\/cse.unl.edu\/~cbourke\/latex\/ComplexityZoo.pdf. 2.1  Scott Aaronson. The Complexity Zoo. Available at http:\/\/cse.unl.edu\/~cbourke\/latex\/ComplexityZoo.pdf. 2.1"},{"key":"e_1_2_1_2_1","first-page":"109","article-title":"A counterexample to the generalized Linial-Nisan conjecture","volume":"17","author":"Aaronson Scott","year":"2010","unstructured":"Scott Aaronson . A counterexample to the generalized Linial-Nisan conjecture . Electronic Colloquium on Computational Complexity , 17 : 109 , 2010 . 2.1 Scott Aaronson. A counterexample to the generalized Linial-Nisan conjecture. Electronic Colloquium on Computational Complexity, 17:109, 2010. 2.1","journal-title":"Electronic Colloquium on Computational Complexity"},{"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.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90036-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_2_1_9_1","first-page":"91","volume-title":"Randomness and Computation","author":"Ben-Or Michael","year":"1990","unstructured":"Michael Ben-Or and Nati Linial . Collective coin ipping . In S. Micali, editor, Randomness and Computation , pages 91 -- 115 . Academic Press , 1990 . 3.1 Michael Ben-Or and Nati Linial. Collective coin ipping. In S. Micali, editor, Randomness and Computation, pages 91--115. Academic Press, 1990. 3.1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00157-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90043-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12133"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032916"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00034-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.35"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_2_1_18_1","volume-title":"Computational Limitations for Small Depth Circuits","author":"H\u00e5stad Johan","year":"1986","unstructured":"Johan H\u00e5stad . Computational Limitations for Small Depth Circuits . MIT Press , Cambridge, MA , 1986 . 1.1, 2, 2.1, 1, 3, 4.1 Johan H\u00e5stad. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA, 1986. 1.1, 2, 2.1, 1, 3, 4.1"},{"key":"e_1_2_1_19_1","first-page":"143","volume-title":"Almost optimal lower bounds for small depth circuits","author":"H\u00e4stad Johan","year":"1989","unstructured":"Johan H\u00e4stad . Almost optimal lower bounds for small depth circuits , pages 143 -- 170 . Advances in Computing Research, Vol. 5 . JAI Press , 1989 . 1.1, 2, 2.1, 1 Johan H\u00e4stad. Almost optimal lower bounds for small depth circuits, pages 143--170. Advances in Computing Research, Vol. 5. JAI Press, 1989. 1.1, 2, 2.1, 1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/181462.181463"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/502976"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/219817.219822"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90011-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_2_1_25_1","series-title":"Math","first-page":"30","volume-title":"Combinatorics, computing and complexity (Tianjing and Beijing","author":"Ko I","year":"1988","unstructured":"Ker- I Ko . Constructing oracles by lower bound techniques for circuits . In Combinatorics, computing and complexity (Tianjing and Beijing , 1988 ), volume 1 of Math . Appl. (Chinese Ser.), pages 30 -- 76 . Kluwer Acad . Publ., Dordrecht, 1989. 2.1, 3 Ker-I Ko. Constructing oracles by lower bound techniques for circuits. In Combinatorics, computing and complexity (Tianjing and Beijing, 1988), volume 1 of Math. Appl. (Chinese Ser.), pages 30--76. Kluwer Acad. Publ., Dordrecht, 1989. 2.1, 3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.228.4698.479"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808717"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1972.29"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394565"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.67"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90010-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1602"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808733"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_36_1","volume-title":"Handbook of Combinatorics","author":"Shmoys David","year":"1995","unstructured":"David Shmoys and \u00c9va Tardos . Computational Complexity . In Handbook of Combinatorics (Ronald Graham, Martin Gr\u00f6tschel, and L\u00e1szlo Lov\u00e1sz, eds.), volume 2 . North-Holland , 1995 . 2.1 David Shmoys and \u00c9va Tardos. Computational Complexity. In Handbook of Combinatorics (Ronald Graham, Martin Gr\u00f6tschel, and L\u00e1szlo Lov\u00e1sz, eds.), volume 2. North-Holland, 1995. 2.1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_38_1","volume-title":"Complexity Theory Column 37: Completeness in the Polynomial-Time Hierarchy: A Compendium. ACM SIGACT News, 33(3):32--49","author":"Sch\u00e4efer Marcus","year":"2002","unstructured":"Marcus Sch\u00e4efer and Chris Umans . Complexity Theory Column 37: Completeness in the Polynomial-Time Hierarchy: A Compendium. ACM SIGACT News, 33(3):32--49 , 2002 . 1 Marcus Sch\u00e4efer and Chris Umans. Complexity Theory Column 37: Completeness in the Polynomial-Time Hierarchy: A Compendium. ACM SIGACT News, 33(3):32--49, 2002. 1"},{"key":"e_1_2_1_39_1","volume-title":"Complexity Theory Column 38: Completeness in the Polynomial-Time Hierarchy: Part II. ACM SIGACT News, 33(4):22--36","author":"Sch\u00e4efer Marcus","year":"2002","unstructured":"Marcus Sch\u00e4efer and Chris Umans . Complexity Theory Column 38: Completeness in the Polynomial-Time Hierarchy: Part II. ACM SIGACT News, 33(4):22--36 , 2002 . 1 Marcus Sch\u00e4efer and Chris Umans. Complexity Theory Column 38: Completeness in the Polynomial-Time Hierarchy: Part II. ACM SIGACT News, 33(4):22--36, 2002. 1"},{"issue":"3","key":"e_1_2_1_40_1","first-page":"553","article-title":"Realizations of linear functions by formulas using _, &","volume":"136","author":"Subbotovskaya Bella","year":"1961","unstructured":"Bella Subbotovskaya . Realizations of linear functions by formulas using _, & , . Doklady Akademii Nauk SSSR , 136 ( 3 ): 553 -- 555 , 1961 . 4.1 Bella Subbotovskaya. Realizations of linear functions by formulas using _, &, . Doklady Akademii Nauk SSSR, 136(3):553--555, 1961. 4.1","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"e_1_2_1_42_1","first-page":"285","volume-title":"Measure One Results in Computational Complexity Theory","author":"Vollmer Heribert","year":"1997","unstructured":"Heribert Vollmer and KlausWagner. Measure One Results in Computational Complexity Theory , pages 285 -- 312 . Advances in Algorithms, Languages, and Complexity. Springer , 1997 . 2.1 Heribert Vollmer and KlausWagner. Measure One Results in Computational Complexity Theory, pages 285--312. Advances in Algorithms, Languages, and Complexity. Springer, 1997. 2.1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2852040.2852052","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2852040.2852052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:17Z","timestamp":1750222457000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2852040.2852052"}},"subtitle":["The Polynomial Hierarchy, Random Oracles, and Boolean Circuits"],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1145\/2852040.2852052"],"URL":"https:\/\/doi.org\/10.1145\/2852040.2852052","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2015,12]]},"assertion":[{"value":"2015-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}