{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:29:08Z","timestamp":1753439348978,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,12,17]],"date-time":"2014-12-17T00:00:00Z","timestamp":1418774400000},"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":["J. ACM"],"published-print":{"date-parts":[[2014,12,17]]},"abstract":"<jats:p>\n            Agrawal and Vinay [2008], Koiran [2012], and Tavenas [2013] have recently shown that an exp (\u03c9(\u221a\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of \u00d7 gates having fanin bounded by \u221an translates to a superpolynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin.\n          <\/jats:p>\n          <jats:p>\n            We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by \u221an computing the permanent (or the determinant) must be of size exp,(\u03a9(\u221a\n            <jats:italic>n<\/jats:italic>\n            )).\n          <\/jats:p>","DOI":"10.1145\/2629541","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T13:38:51Z","timestamp":1418996331000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Approaching the Chasm at Depth Four"],"prefix":"10.1145","volume":"61","author":[{"given":"Ankit","family":"Gupta","sequence":"first","affiliation":[{"name":"Microsoft Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pritish","family":"Kamath","sequence":"additional","affiliation":[{"name":"Microsoft Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neeraj","family":"Kayal","sequence":"additional","affiliation":[{"name":"Microsoft Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramprasad","family":"Saptharishi","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/00927879008824043"},{"key":"e_1_2_1_3_1","unstructured":"David A. Cox John B. Little and Donal O'Shea. 2007. Ideals Varieties and Algorithms. Springer.   David A. Cox John B. Little and Donal O'Shea. 2007. Ideals Varieties and Algorithms. Springer."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Herv\u00e9 Fournier Nutan Limaye Guillaume Malod and Srikanth Srinivasan. 2013. Lower bounds for depth 4 formulas computing iterated matrix multiplication. Electronic Colloquium on Computational Complex. (ECCC) 100.  Herv\u00e9 Fournier Nutan Limaye Guillaume Malod and Srikanth Srinivasan. 2013. Lower bounds for depth 4 formulas computing iterated matrix multiplication. Electronic Colloquium on Computational Complex. (ECCC) 100.","DOI":"10.1145\/2591796.2591824"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276872"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002009900021"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214036"},{"key":"e_1_2_1_9_1","unstructured":"Neeraj Kayal. 2012b. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC). 19.  Neeraj Kayal. 2012b. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC). 19."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal Chandan Saha and Ramprasad Saptharishi. 2013. A super-polynomial lower bound for regular arithmetic formulas. Electronic Colloquium on Computational Complexity (ECCC). 20.  Neeraj Kayal Chandan Saha and Ramprasad Saptharishi. 2013. A super-polynomial lower bound for regular arithmetic formulas. Electronic Colloquium on Computational Complexity (ECCC). 20.","DOI":"10.1145\/2591796.2591847"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_12_1","first-page":"68","article-title":"Lower bounds for depth 4 homogenous circuits with bounded top fanin","volume":"20","author":"Kumar Mrinal","year":"2013","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(86)90134-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502797"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2000.12005235"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001609"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02571229"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_71"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629541","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,17]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12,17]]}},"alternative-id":["10.1145\/2629541"],"URL":"https:\/\/doi.org\/10.1145\/2629541","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,12,17]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}