{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:17Z","timestamp":1784110337107,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"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":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806781","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"667-676","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Non-commutative circuits and the sum-of-squares problem"],"prefix":"10.1145","author":[{"given":"Pavel","family":"Hrube\u0161","sequence":"first","affiliation":[{"name":"Institute for Advanced Study, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amir","family":"Yehudayoff","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/308215.308225"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"W. Baur and V. Strassen. The complexity of partial derivatives. Theoretical computer science (22) pages 317--330 1983.  W. Baur and V. Strassen. The complexity of partial derivatives. Theoretical computer science (22) pages 317--330 1983.","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"P. Burgisser. Completeness and reduction in algebraic complexity theory. Springer-Verlag Berlin Heidelberg 2000.  P. Burgisser. Completeness and reduction in algebraic complexity theory. Springer-Verlag Berlin Heidelberg 2000.","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447359"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509944"},{"key":"e_1_3_2_1_6_1","author":"von zur Gathen J.","year":"1988","journal-title":"Ann. Rev. Comp. Sci. (3), pages 317--347"},{"key":"e_1_3_2_1_7_1","first-page":"241","volume-title":"Algebraic Methods in Graph Theory","author":"Godsil C.","year":"1981"},{"issue":"2","key":"e_1_3_2_1_8_1","first-page":"120","volume":"8","author":"Hyafil L.","year":"1979","journal-title":"J. Comput."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0007-3"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.34"},{"key":"e_1_3_2_1_11_1","first-page":"309","volume-title":"Nach. Ges. der Wiss. G\u00f6ttingen","author":"Hurwitz A.","year":"1898"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448439"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1963-10930-1"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_3_2_1_15_1","unstructured":"S. Jukna Boolean function complexity: advances and frontiers. Book in preparation.   S. Jukna Boolean function complexity: advances and frontiers. Book in preparation."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222021"},{"key":"e_1_3_2_1_17_1","first-page":"447","volume":"33","author":"Kirkman T.","year":"1848","journal-title":"Philos.Mag. (ser. 3)"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388517"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/44.2.215"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"A. Pfister. Zur Darstellung definiter Funktionen als Summe von Quadraten. ph Inventiones Mathematicae. 1967.  A. Pfister. Zur Darstellung definiter Funktionen als Summe von Quadraten. ph Inventiones Mathematicae. 1967.","DOI":"10.1007\/BF01425382"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"J. Radon. Lineare scharen orthogonalen matrizen. Abh. Math. Sem. Univ. Hamburg 1 pages 2--14 1922.  J. Radon. Lineare scharen orthogonalen matrizen. Abh. Math. Sem. Univ. Hamburg 1 pages 2--14 1922.","DOI":"10.1007\/BF02940576"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374479"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.8"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707932"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"D. B. Shapiro. Composition of quadratic forms. W. de Gruyter Verlag 2000.  D. B. Shapiro. Composition of quadratic forms. W. de Gruyter Verlag 2000.","DOI":"10.1515\/9783110824834"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":". Strassen. Die berechnungskomplexitat von elementarsymmetrischen funktionen und von interpolationskoeffizienten. Numerische Mathematik (20) pages 238--251 1973.  . Strassen. Die berechnungskomplexitat von elementarsymmetrischen funktionen und von interpolationskoeffizienten. Numerische Mathematik (20) pages 238--251 1973.","DOI":"10.1007\/BF01436566"},{"key":"e_1_3_2_1_31_1","first-page":"182","volume":"264","author":"V. Strassen. Vermeidung von Division","year":"1973","journal-title":"Angew. Math."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"S. Winograd. On the number of multiplications needed to compute certain functions. Comm. on Pure and Appl. Math. (23) pages 165--179 1970.  S. Winograd. On the number of multiplications needed to compute certain functions. Comm. on Pure and Appl. Math. (23) pages 165--179 1970.","DOI":"10.1002\/cpa.3160230204"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1987-045-6"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/41.4.463"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"S. Yuzvinsky. A series of monomial pairings. phLinear and multilinear algebra 15 pages 19--119 1984.  S. Yuzvinsky. A series of monomial pairings. phLinear and multilinear algebra 15 pages 19--119 1984.","DOI":"10.1080\/03081088408817582"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","location":"Cambridge Massachusetts USA","acronym":"STOC'10","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806781","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":35,"alternative-id":["10.1145\/1806689.1806781","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806781","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}