{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:04Z","timestamp":1787340604837,"version":"build-2736575974"},"reference-count":23,"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":[[1982,8]]},"abstract":"<jats:p>A property of Boolean functions of n variables is described and shown to imply lower bounds as large as $\\Omega (n\\log n)$ on the number of literals in any Boolean formula for any function with the property. Formulas over the full basis of binary operations $( \\wedge , \\oplus ,{\\text{ etc.}})$ are considered. The lower bounds apply to all but a vanishing fraction of symmetric functions, in particular, to all threshold functions with sufficiently large threshold and to the \u201ccongruent to zero modulo k\u201d function for $k &gt; 2$. In the case $k = 4$, the bound is optimal.<\/jats:p>","DOI":"10.1137\/0211033","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:24:24Z","timestamp":1109226264000},"page":"416-427","source":"Crossref","is-referenced-by-count":25,"title":["$\\Omega (n\\log n)$ Lower Bounds on Length of Boolean Formulas"],"prefix":"10.1137","volume":"11","author":[{"given":"Michael J.","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albert R.","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael S.","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Michael J. Fischer, Albert R. Meyer, Michael S. Paterson,  Lower bounds on the size of Boolean formulas: preliminary report,  Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N. M., 1975), Assoc. Comput. Mach., New York,  1975,  37\u201344 55:117040381.94028","DOI":"10.1145\/800116.803751"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321574.321587"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70524-X"},{"key":"R5","first-page":"1149","volume":"14","author":"Khasin L. S.","year":"1969","journal-title":"Soviet Physics Dokl."},{"key":"R6","first-page":"35","volume":"1","author":"Khrapchenko V. M.","year":"1971","journal-title":"Mat. Zametki 9"},{"key":"R7","first-page":"109","volume":"11","author":"Hrapcenko V. M.","year":"1972","journal-title":"Mat. Zametki"},{"key":"R8","first-page":"231","volume":"31","author":"Khrapchenko V. M.","year":"1976","journal-title":"Problemy Kibernet"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90021-X"},{"key":"R10","volume-title":"The Art of Computer Programming, Vol. 1, Fundamental Algorithms","author":"Knuth D. E.","year":"1973"},{"key":"R11","first-page":"458","volume-title":"Prob. Cybernetics II","author":"Krichevskii R. E.","year":"1961"},{"key":"R12","first-page":"61","volume":"3","author":"Lupanov O. B.","year":"1960","journal-title":"Probl. Kibernet"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264601"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90038-7"},{"key":"R15","first-page":"765","volume":"169","author":"Neciporuk E. I.","year":"1966","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"R16","volume-title":"Journ\u00e9es algorithmiques (\u00c9cole Norm. Sup., Paris, 1975)","author":"Paterson Michael S.","year":"1976"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08138-0_2"},{"key":"R18","unstructured":"G. L. Peterson,  An upper bound on the size of formulae for symmetric Boolean functions, Tech. Report, 78-03-01, Dept. Computer Science, Univ. of Washington, Seattle,  1978, extended abstract"},{"key":"R19","unstructured":"N. Pippenger,  Short formulae for symmetric functions, Research Report, RC-5143, IBM, Yorktown Heights, NY,  1974"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"N. Pippenger,  The realization of monotone Boolean functions,  Proc. 8th Annual ACM Symposium on Theory of Computing,  1976,  204\u2013209 0366.94050","DOI":"10.1145\/800113.803650"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1002\/sapm194221183"},{"key":"R22","unstructured":"B. Vilfan,  The complexity of finite functions, Tech. Rep., 97, Dept. Electrical Engineering, Project MAC, Massachusetts Institute of Technology, Cambridge, MA,  1972"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90035-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0211033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:41:10Z","timestamp":1787337670000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0211033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,8]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,8]]}},"alternative-id":["10.1137\/0211033"],"URL":"https:\/\/doi.org\/10.1137\/0211033","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,8]]}}}