{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:08Z","timestamp":1750306628568,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,5,31]],"date-time":"2014-05-31T00:00:00Z","timestamp":1401494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NRF"},{"name":"GA CR","award":["P202\/12\/G061"],"award-info":[{"award-number":["P202\/12\/G061"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0832797"],"award-info":[{"award-number":["CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"name":"RVO","award":["67985840"],"award-info":[{"award-number":["67985840"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,5,31]]},"DOI":"10.1145\/2591796.2591856","type":"proceedings-article","created":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T12:01:58Z","timestamp":1443700918000},"page":"213-222","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Toward better formula lower bounds"],"prefix":"10.1145","author":[{"given":"Dmitry","family":"Gavinsky","sequence":"first","affiliation":[{"name":"Institute of Mathematics, Academy of Sciences, Czech Republic"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ"}]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ"}]}],"member":"320","published-online":{"date-parts":[[2014,5,31]]},"reference":[{"issue":"1","key":"e_1_3_2_2_1_1","first-page":"24","article-title":"On a method for obtaining more than quadratic effective lower bounds for the complexity of π-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 π-schemes . Moscow University Mathematics Bulletin , 42 ( 1 ): 24 -- 29 , 1987 . A. E. Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow University Mathematics Bulletin, 42(1):24--29, 1987.","journal-title":"Moscow University Mathematics Bulletin"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90093-0"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214025"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_39"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875561"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/129837"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.10.006"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8195-x"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050045"},{"key":"e_1_3_2_2_14_1","volume-title":"Toward better formula lower bounds: An information complexity approach to the krw composition conjecture. Electronic Colloquium on Computational Complexity (ECCC), (190)","author":"Gavinsky D.","year":"2013","unstructured":"D. Gavinsky , O. Meir , O. Weinstein , and A. Wigderson . Toward better formula lower bounds: An information complexity approach to the krw composition conjecture. Electronic Colloquium on Computational Complexity (ECCC), (190) , 2013 . D. Gavinsky, O. Meir, O. Weinstein, and A. Wigderson. Toward better formula lower bounds: An information complexity approach to the krw composition conjecture. Electronic Colloquium on Computational Complexity (ECCC), (190), 2013."},{"key":"e_1_3_2_2_15_1","first-page":"294","volume-title":"Structure in Complexity Theory Conference","author":"Grigni M.","year":"1991","unstructured":"M. Grigni and M. Sipser . Monotone separation of logspace from nc . In Structure in Complexity Theory Conference , pages 294 -- 298 , 1991 . M. Grigni and M. Sipser. Monotone separation of logspace from nc. In Structure in Complexity Theory Conference, pages 294--298, 1991."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2034824"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/013\/07"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759242"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780640"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206317"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"e_1_3_2_2_23_1","volume-title":"Lower bounds on information complexity via zero-communication protocols and applications. Electronic Colloquium on Computational Complexity (ECCC), 19:38","author":"Kerenidis I.","year":"2012","unstructured":"I. Kerenidis , S. Laplante , V. Lerays , J. Roland , and D. Xiao . Lower bounds on information complexity via zero-communication protocols and applications. Electronic Colloquium on Computational Complexity (ECCC), 19:38 , 2012 . I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. Lower bounds on information complexity via zero-communication protocols and applications. Electronic Colloquium on Computational Complexity (ECCC), 19:38, 2012."},{"key":"e_1_3_2_2_24_1","first-page":"474","article-title":"A method of obtaining lower bounds for the complexity of π-schemes","volume":"10","author":"Khrapchenko V. M.","year":"1972","unstructured":"V. M. Khrapchenko . A method of obtaining lower bounds for the complexity of π-schemes . Mathematical Notes Academy of Sciences USSR , 10 : 474 -- 479 , 1972 . V. M. Khrapchenko. A method of obtaining lower bounds for the complexity of π-schemes. Mathematical Notes Academy of Sciences USSR, 10:474--479, 1972.","journal-title":"Mathematical Notes Academy of Sciences USSR"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_2_27_1","first-page":"525","volume-title":"Proceedings of the Fourth Hawaii International Symposium on System Sciences","author":"Spira P. M.","year":"1971","unstructured":"P. M. Spira . On time-hardware complexity tradeoffs for boolean functions . In Proceedings of the Fourth Hawaii International Symposium on System Sciences , pages 525 -- 527 , 1971 . P. M. Spira. On time-hardware complexity tradeoffs for boolean functions. In Proceedings of the Fourth Hawaii International Symposium on System Sciences, pages 525--527, 1971."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/35517"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"event":{"name":"STOC '14: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York","acronym":"STOC '14"},"container-title":["Proceedings of the forty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591856","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591796.2591856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:55:45Z","timestamp":1750229745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591856"}},"subtitle":["an information complexity approach to the KRW composition conjecture"],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":29,"alternative-id":["10.1145\/2591796.2591856","10.1145\/2591796"],"URL":"https:\/\/doi.org\/10.1145\/2591796.2591856","relation":{},"subject":[],"published":{"date-parts":[[2014,5,31]]},"assertion":[{"value":"2014-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}