{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:14Z","timestamp":1787340554267,"version":"build-2736575974"},"reference-count":10,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>We establish a lower bound for the formula size of quolynomials over arbitrary fields. Our basic formula operations are addition, subtraction, multiplication and division. The proof is based on Ne\u010diporuk\u2019s [Soviet Math. Doklady, 7 (1966), pp. 999\u20131000] lower bound for Boolean functions and uses formal power series. This result immediately yields a lower bound for the formula size of rational functions over infinite fields. We also show how to adapt Ne\u010diporuk\u2019s method to rational functions over finite fields. These results are then used to show that, over any field, the $n \\times n$ determinant function has formula size at least $\\Omega (n^3 )$. We thus have an algebraic analogue to the $\\Omega (n^3 )$ lower bound for the Boolean determinant due to Kloss [Soviet Math. Doklady, 7 (1966), pp. 1537\u20131540].<\/jats:p>","DOI":"10.1137\/0214050","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"678-687","source":"Crossref","is-referenced-by-count":35,"title":["A Lower Bound for the Formula Size of Rational Functions"],"prefix":"10.1137","volume":"14","author":[{"given":"K. A.","family":"Kalorkoti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90766-5"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804347"},{"key":"R4","first-page":"781","volume":"171","author":"Kloss B. M.","year":"1966","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"R5","first-page":"765","volume":"169","author":"Ne\u010diporuk \u00c8. I.","year":"1966","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"R6","volume-title":"The complexity of computing","author":"Savage John E.","year":"1976"},{"key":"R7","first-page":"184","volume":"264","author":"Strassen Volker","year":"1973","journal-title":"J. Reine Angew. Math."},{"key":"R8","volume-title":"Modern Algebra, Vols I, II","author":"van der Waerden B. L.","year":"1949"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-29244-0"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-29244-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:14Z","timestamp":1787337554000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214050"],"URL":"https:\/\/doi.org\/10.1137\/0214050","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}