{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:28:34Z","timestamp":1771486114881,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":365,"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1212372"],"award-info":[{"award-number":["CCF-1212372"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["FG-BR2013-112"],"award-info":[{"award-number":["FG-BR2013-112"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897636","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T09:04:07Z","timestamp":1465549447000},"page":"633-643","update-policy":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits"],"prefix":"10.1145","author":[{"given":"Daniel M.","family":"Kane","sequence":"first","affiliation":[{"name":"University of California at San Diego, USA"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722146"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.19"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_11"},{"key":"e_1_3_2_1_6_1","first-page":"63","article-title":"On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0-schemes","volume":"42","author":"Andreev A. E.","year":"1987","unstructured":"A. E. Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0-schemes. Moscow Univ. Math. Bull., 42:63\u201366, 1987.","journal-title":"Moscow Univ. Math. Bull."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0100-0"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_15"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24318-4_4"},{"key":"e_1_3_2_1_10_1","volume-title":"Average-case lower bounds and satisfiability algorithms for small threshold circuits. Electronic Colloquium on Computational Complexity (ECCC), 22:191","author":"Chen R.","year":"2015","unstructured":"R. Chen, R. Santhanam, and S. Srinivasan. Average-case lower bounds and satisfiability algorithms for small threshold circuits. Electronic Colloquium on Computational Complexity (ECCC), 22:191, 2015. To appear in CCC\u201916."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1961.24"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646839.708661"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200426"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54233-7_176"},{"key":"e_1_3_2_1_17_1","first-page":"220","article-title":"A linear lower bound for the size of threshold circuits","volume":"50","author":"Gr\u00f6ger H. D.","year":"1993","unstructured":"H. D. Gr\u00f6ger and G. Tur\u00e1n. A linear lower bound for the size of threshold circuits. Bull. of the EATCS, 50:220\u2013221, 1993.","journal-title":"Bull. of the EATCS"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.33"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_46"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/120897432"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.78"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1988.5260"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792282965"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.58"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1984890"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488630"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.69"},{"key":"e_1_3_2_1_31_1","first-page":"277","article-title":"On the number of real roots of a random algebraic equation III","volume":"12","author":"Littlewood J.","year":"1943","unstructured":"J. Littlewood and C. Offord. On the number of real roots of a random algebraic equation III. Mat. USSR Sb., 12:277\u2013285, 1943.","journal-title":"Mat. USSR Sb."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478259"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1096885"},{"key":"e_1_3_2_1_34_1","volume-title":"Threshold Logic and its Applications","author":"Muroga S.","year":"1971","unstructured":"S. Muroga. Threshold Logic and its Applications. John Wiley & Sons, Inc., 1971."},{"key":"e_1_3_2_1_35_1","first-page":"315","volume-title":"Proceedings of \u201cCombinatorics, Paul Erdos is Eighty\u201d","author":"Nisan N.","year":"1994","unstructured":"N. Nisan. The communication complexity of threshold gates. In Proceedings of \u201cCombinatorics, Paul Erdos is Eighty\u201d, pages 301\u2013315, 1994."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756466"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040203"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1059"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374480"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.67"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.312169"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-2696-4_1"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.25"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0067-7"},{"key":"e_1_3_2_1_45_1","first-page":"110","article-title":"Realizations of linear functions by formulas using +,*,-","volume":"2","author":"Subbotovskaya B. A.","year":"1961","unstructured":"B. A. Subbotovskaya. Realizations of linear functions by formulas using +,*,-. Soviet Mathematics Doklady, 2:110\u2013112, 1961.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591858"},{"key":"e_1_3_2_1_47_1","unstructured":"R. O. Winder. Threshold Logic. PhD thesis Princeton University 1962. Preliminary version in FOCS\u201960."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/4479.4487"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/2897518.2897636","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897636","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897636","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:40:41Z","timestamp":1763458841000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/2897518.2897636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":48,"alternative-id":["10.1145\/2897518.2897636","10.1145\/2897518"],"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/2897518.2897636","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}