{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:15Z","timestamp":1775282295463,"version":"3.50.1"},"reference-count":5,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5031,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1993,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the formula size complexity of boolean functions over the base consisting of \u2227, \u2228, and \u00ac gates. In 1961 Subbotovskaya proved that, for any boolean function on <jats:italic>n<\/jats:italic> variables, setting all but a randomly chosen \u03f5<jats:italic>n<\/jats:italic> variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of \u03a9(<jats:italic>n<\/jats:italic><jats:sup>1.5<\/jats:sup>) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of \u03a9<jats:italic>C<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2.5<\/jats:sup>\/log<jats:sup><jats:italic>O<\/jats:italic>(1)<\/jats:sup>(<jats:italic>n<\/jats:italic>)) for a function in <jats:italic>P<\/jats:italic>. We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an <jats:italic>O<\/jats:italic>(\u03f5<jats:sup>\u03b3<\/jats:sup>) franction of its original complexity, for<\/jats:p><jats:p><jats:chem-struct-wrap><jats:chem-struct><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\/gif\" position=\"anchor\" specific-use=\"enlarged-web-image\" xlink:href=\"graphic\/must001.gif\"><jats:alt-text>magnified image<\/jats:alt-text><\/jats:graphic><\/jats:chem-struct><\/jats:chem-struct-wrap><\/jats:p><jats:p>This allows us to give an improved lower bound of \u03a9(<jats:italic>n<\/jats:italic><jats:sup>2.556\u2026<\/jats:sup>) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. \u00a9 1993 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240040202","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T18:18:51Z","timestamp":1180203531000},"page":"121-133","source":"Crossref","is-referenced-by-count":34,"title":["The effect of random restrictions on formula size"],"prefix":"10.1002","volume":"4","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"issue":"1","key":"e_1_2_1_2_2","first-page":"63","article-title":"On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0\u2010schemes","volume":"42","author":"Andreev A. E.","year":"1987","journal-title":"Moscow Univ. Math. Bull."},{"key":"e_1_2_1_3_2","unstructured":"R.BoppanaandM.Sipser The complexity of finite functions inHandbook of Theoretical Computer Science."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01747074"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040203"},{"key":"e_1_2_1_6_2","first-page":"110","article-title":"Realizations of linear functions by formulas using +, *, \u2010","volume":"2","author":"Subbotovskaya B. A.","year":"1961","journal-title":"Sov. Math. Doklady"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240040202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240040202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T10:58:41Z","timestamp":1697453921000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240040202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1]]},"references-count":5,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,1]]}},"alternative-id":["10.1002\/rsa.3240040202"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240040202","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,1]]}}}