THE SHRINKAGE EXPONENT OF DE MORGAN FORMULAS IS 2

Authors
HASTAD J
Citation
J. Hastad, THE SHRINKAGE EXPONENT OF DE MORGAN FORMULAS IS 2, SIAM journal on computing, 27(1), 1998, pp. 48-64
Citations number
13
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
27
Issue
1
Year of publication
1998
Pages
48 - 64
Database
ISI
SICI code
0097-5397(1998)27:1<48:TSEODM>2.0.ZU;2-L
Abstract
We prove that if we hit a de Morgan formula of size L with a random re striction from R-p, then the expected remaining size is at most O(p(2) (log 1/p)(3/2) L + p root L). As a corollary we obtain an Omega(n(3-o (1)))-formula-size lower bound for an explicit function in P. This is the strongest known lower bound for any explicit function in NP.