{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:24:01Z","timestamp":1750307041001,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214023","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"479-494","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates"],"prefix":"10.1145","author":[{"given":"Anna","family":"G\u00e1l","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}]},{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, the Academy of Sciences of the Czech Republic, Prague, Czech Rep"}]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, the Academy of Sciences of the Czech Republic, Prague, Czech Rep"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28410"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80027-3"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.2008114"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.847727"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00131-2"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405292"},{"key":"e_1_3_2_2_8_1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BFb0036901","volume-title":"10th Colloquium on Automata, Languages and Programming (ICALP'83)","author":"Chandra A. K.","year":"1983","unstructured":"A. K. Chandra , S. Fortune , and R. J. Lipton . Lower bounds for constant depth circuits for prefix problems . In 10th Colloquium on Automata, Languages and Programming (ICALP'83) , volume 154 of LNCS , pages 109 -- 117 . Springer , 1983 . A. K. Chandra, S. Fortune, and R. J. Lipton. Lower bounds for constant depth circuits for prefix problems. In 10th Colloquium on Automata, Languages and Programming (ICALP'83), volume 154 of LNCS, pages 109--117. Springer, 1983."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.55"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808731"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_30"},{"key":"e_1_3_2_2_13_1","volume-title":"Flows in networks","author":"Ford L. R.","year":"1962","unstructured":"L. R. Ford and D. R. Fulkerson . Flows in networks . Princeton University Press , 1962 . L. R. Ford and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962."},{"key":"e_1_3_2_2_14_1","first-page":"177","volume-title":"2nd International Symposium on Information Theory","author":"Gelfand S.","year":"1973","unstructured":"S. Gelfand , R. Dobrushin , and M. Pinsker . On the complexity of coding . In 2nd International Symposium on Information Theory , pages 177 -- 184 . Akademiai Kiado , 1973 . S. Gelfand, R. Dobrushin, and M. Pinsker. On the complexity of coding. In 2nd International Symposium on Information Theory, pages 177--184. Akademiai Kiado, 1973."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875548"},{"key":"e_1_3_2_2_16_1","first-page":"6037","article-title":"Nombre minimal de contacts de fermature n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables","volume":"258","author":"Hansel G.","year":"1964","unstructured":"G. Hansel . Nombre minimal de contacts de fermature n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables . C. R. Acad. Sci. Paris , 258 : 6037 -- 6040 , 1964 . G. Hansel. Nombre minimal de contacts de fermature n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables. C. R. Acad. Sci. Paris, 258:6037--6040, 1964.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374438"},{"key":"e_1_3_2_2_18_1","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity: Advances and Frontiers","author":"Jukna S.","year":"2012","unstructured":"S. Jukna . Boolean Function Complexity: Advances and Frontiers , volume 27 of Algorithms and Combinatorics . Springer , 2012 . S. Jukna. Boolean Function Complexity: Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210136"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.11"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90257-T"},{"key":"e_1_3_2_2_23_1","first-page":"556","volume-title":"9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98)","author":"Miltersen P. B.","year":"1998","unstructured":"P. B. Miltersen . Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries . In 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98) , pages 556 -- 563 . ACM Press , 1998 . P. B. Miltersen. Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98), pages 556--563. ACM Press, 1998."},{"key":"e_1_3_2_2_24_1","volume-title":"Matroid theory","author":"Oxley J. G.","year":"1992","unstructured":"J. G. Oxley . Matroid theory . Oxford University Press , 1992 . J. G. Oxley. Matroid theory. Oxford University Press, 1992."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(68)90163-7"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215351"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00115-Y"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_3_2_2_29_1","volume-title":"Massachusetts Institute of Technology","author":"Spielman D.","year":"1995","unstructured":"D. Spielman . Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis , Massachusetts Institute of Technology , 1995 . D. Spielman. Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis, Massachusetts Institute of Technology, 1995."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803752"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0187-1"},{"key":"e_1_3_2_2_33_1","volume-title":"Matroid theory","author":"Welsh D. J.","year":"1976","unstructured":"D. J. Welsh . Matroid theory . Academic Press , London , 1976 . D. J. Welsh. Matroid theory. Academic Press, London, 1976."}],"event":{"name":"STOC'12: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York USA","acronym":"STOC'12"},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214023","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":33,"alternative-id":["10.1145\/2213977.2214023","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214023","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}