{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T21:02:30Z","timestamp":1767992550028,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":30,"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.2214035","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"625-642","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Reconstruction of depth-4 multilinear circuits with top fan-in 2"],"prefix":"10.1145","author":[{"given":"Ankit","family":"Gupta","sequence":"first","affiliation":[{"name":"Microsoft Research India, Bangalore, India"}]},{"given":"Neeraj","family":"Kayal","sequence":"additional","affiliation":[{"name":"Microsoft Research India, Bangalore, India"}]},{"given":"Satya","family":"Lokam","sequence":"additional","affiliation":[{"name":"Microsoft Research India, Bangalore, India"}]}],"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\/12130.12166"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0299-8"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337257"},{"key":"e_1_3_2_2_6_1","volume-title":"varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra","author":"Cox D. A.","year":"1997","unstructured":"D. A. Cox , J. Little , and D. O'Shea . Ideals , varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra . Springer , second edition, 1997 . D. A. Cox, J. Little, and D. O'Shea. Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra. Springer, second edition, 1997."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796419"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.70"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_3_2_2_13_1","first-page":"375","volume-title":"Randomness and Computation","author":"Kaltofen E.","year":"1989","unstructured":"E. Kaltofen . Factorization of polynomials given by straight-line programs . In Randomness and Computation , pages 375 -- 412 . JAI Press , 1989 . E. Kaltofen. Factorization of polynomials given by straight-line programs. In Randomness and Computation, pages 375--412. JAI Press, 1989."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806779"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.18"},{"key":"e_1_3_2_2_17_1","volume-title":"Affine projections of polynomials. Electronic Colloquium on Computational Complexity (ECCC), 18:61","author":"Kayal N.","year":"2011","unstructured":"N. Kayal . Affine projections of polynomials. Electronic Colloquium on Computational Complexity (ECCC), 18:61 , 2011 . N. Kayal. Affine projections of polynomials. Electronic Colloquium on Computational Complexity (ECCC), 18:61, 2011."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a010"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380801"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374479"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993693"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070694879"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_52"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"R.\n      Zippel\n    . \n      Probabilistic\n     algorithms for sparse polynomials.\n   In E. W. Ng editor EUROSAM volume \n  72\n   of \n  Lecture Notes in Computer Science pages \n  216\n  --\n  226\n  . \n  Springer 1979\n  .   R. Zippel. Probabilistic algorithms for sparse polynomials. In E. W. Ng editor EUROSAM volume 72 of Lecture Notes in Computer Science pages 216--226. Springer 1979.","DOI":"10.1007\/3-540-09519-5_73"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.2214035","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214035","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.2214035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":30,"alternative-id":["10.1145\/2213977.2214035","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214035","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"}}]}}