Premium
Shrinkage of de Morgan formulae under restriction
Author(s) -
Paterson Michael S.,
Zwick Uri
Publication year - 1993
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240040203
Subject(s) - exponent , upper and lower bounds , combinatorics , mathematics , function (biology) , basis (linear algebra) , shrinkage , statistics , mathematical analysis , geometry , philosophy , linguistics , evolutionary biology , biology
Abstract It is shown that a random restriction leaving only a fraction ϵ of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O ( E (5−√2)/2 ) = O (ϵ 1.63 ). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long‐standing result of O (ϵ 1.5 ) by Subbotovskaya and a recent improvement to O (ϵ (21−√73)/8 ) = O (ϵ 1.55 ) by Nisan and Impagliazzo. The New exponent yields an increased lower bound of n (7−√3)/2− o (1) = Ω( n 2.63 ) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP. © 1993 John Wiley & Sons, Inc.