{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:55:06Z","timestamp":1781078106757,"version":"3.54.1"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,12,26]],"date-time":"2016-12-26T00:00:00Z","timestamp":1482710400000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"\n For a Boolean function\n f<\/jats:italic>\n : {0, 1}\n \n n<\/jats:italic>\n <\/jats:sup>\n \u2192 {0, 1}, let\n f\u02c6<\/jats:italic>\n be the unique multilinear polynomial such that\n f<\/jats:italic>\n (\n x<\/jats:italic>\n ) =\n f\u02c6<\/jats:italic>\n (\n x<\/jats:italic>\n ) holds for every\n x<\/jats:italic>\n \u02c6 {0, 1}\n \n n<\/jats:italic>\n <\/jats:sup>\n . We show that, assuming VP \u2260 VNP, there exists a polynomial-time computable\n f<\/jats:italic>\n such that\n f\u02c6<\/jats:italic>\n requires superpolynomial arithmetic circuits. In fact, this\n f<\/jats:italic>\n can be taken as a monotone 2-CNF, or a product of affine functions.\n <\/jats:p>\n \n This holds over any field. To prove the results in characteristic 2, we design new VNP-complete families in this characteristic. This includes the polynomial EC\n \n n<\/jats:italic>\n <\/jats:sub>\n counting edge covers in a graph and the polynomial mclique\n \n n<\/jats:italic>\n <\/jats:sub>\n counting cliques in a graph with deleted perfect matching. They both correspond to polynomial-time decidable problems, a phenomenon previously encountered only in characteristic \u2260 2.\n <\/jats:p>","DOI":"10.1145\/2940323","type":"journal-article","created":{"date-parts":[[2016,12,27]],"date-time":"2016-12-27T13:51:31Z","timestamp":1482846691000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On Hardness of Multilinearization and VNP-Completeness in Characteristic 2"],"prefix":"10.1145","volume":"9","author":[{"given":"P.","family":"Hrube\u0161","sequence":"first","affiliation":[{"name":"Institute of Mathematics of ASCR, Prague, Praha, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,12,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_17"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04179-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a008"},{"key":"e_1_2_1_5_1","unstructured":"M. Jerrum. 1981. On the Complexity of Evaluating Multivariate Polynomials. Ph.D. Dissertation. Department of Computer Science University of Edinburgh. M. Jerrum. 1981. On the Complexity of Evaluating Multivariate Polynomials. Ph.D. Dissertation. Department of Computer Science University of Edinburgh."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0263-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.33"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_9_1","first-page":"182","article-title":"Vermeidung von divisionen","volume":"264","author":"Strassen V.","year":"1973","journal-title":"Journal fur die reine angewandte Mathematik"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55808-X_10"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2940323","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2940323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:27Z","timestamp":1750222587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2940323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,26]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/2940323"],"URL":"https:\/\/doi.org\/10.1145\/2940323","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,26]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}