{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T05:03:50Z","timestamp":1782536630237,"version":"3.54.5"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"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":[[2020,3,31]]},"abstract":"\n We show that over the field of complex numbers,\n every<\/jats:italic>\n homogeneous polynomial of degree\n d<\/jats:italic>\n can be approximated (in the border complexity sense) by a depth-3 arithmetic circuit of top fan-in at most 2. This is quite surprising, since there exist homogeneous polynomials\n P<\/jats:italic>\n on\n n<\/jats:italic>\n variables of degree 2, such that any depth-3 arithmetic circuit computing\n P<\/jats:italic>\n must have top fan-in at least \u03a9 (\n n<\/jats:italic>\n ).\n <\/jats:p>\n \n As an application, we get a new tradeoff between the top fan-in and formal degree in an approximate analog of the celebrated depth reduction result of Gupta, Kamath, Kayal, and Saptharishi\u00a0[7, 10]. Formally, we show that if a degree\n d<\/jats:italic>\n homogeneous polynomial\n P<\/jats:italic>\n can be computed by an arithmetic circuit of size\n s<\/jats:italic>\n \u2265\n d<\/jats:italic>\n , then for every\n t<\/jats:italic>\n \u2264\n d<\/jats:italic>\n ,\n P<\/jats:italic>\n is in the border of a depth-3 circuit of top fan-in\n \n s\n \n O(\n t<\/jats:italic>\n )\n <\/jats:sup>\n <\/jats:italic>\n and formal degree\n \n s\n \n O(\n d\/t<\/jats:italic>\n )\n <\/jats:sup>\n <\/jats:italic>\n . To the best of our knowledge, the upper bound on the top fan-in in the original proof of Reference\u00a0[7] is always at least\n s<\/jats:italic>\n \n \u03a9\n (\u221ad)<\/jats:italic>\n <\/jats:sup>\n , regardless of the formal degree.\n <\/jats:p>","DOI":"10.1145\/3371506","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T12:28:17Z","timestamp":1582633697000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Power of Border of Depth-3 Arithmetic Circuits"],"prefix":"10.1145","volume":"12","author":[{"given":"Mrinal","family":"Kumar","sequence":"first","affiliation":[{"name":"IIT Bombay, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,2,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Agrawal Manindra","year":"2008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0114-7"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC\u201988)","author":"Ben-Or Michael","year":"1988"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115473.3115783"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.04.006"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1994.11996185"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/140957123"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00021-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209663"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:23Z","timestamp":1750203863000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,11]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3371506"],"URL":"https:\/\/doi.org\/10.1145\/3371506","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,11]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}