The Library
Shrinkage of de Morgan formulae under restriction
Tools
Paterson, Michael S. and Zwick, Uri (1991) Shrinkage of de Morgan formulae under restriction. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

PDF (Department of Computer Science Research Report)
WRAP_csrr171.pdf  Other  Requires a PDF viewer. Download (4Mb)  Preview 
Abstract
It is shown that a random restriction leaving only a fraction epsilon of the input variables unassigned reduces the expected de Morgan formula size of the induced function by at least a factor of epsilon((5sqrt(3))/2) ~= epsilon 1.63. (A de Morgan formula is a formula over the basis {/\, \/, ~}.) This improves a longstanding result of epsilon 1.5 by Subbotovskaya and a recent improvement to epsilon((21sqrt(73))/8) ~= epsilon 1.55 by Nisan and Impagliazzo. The new exponent yields an increased lower bound of omega(n((7sqrt(3))/2O(1)) for the de Morgan formula size of a function defined by Andreev. This is the largest lower bound known for a function in NP.
Item Type:  Report  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Proposition (Logic)  
Series Name:  Department of Computer Science research report  
Publisher:  University of Warwick. Department of Computer Science  
Official Date:  January 1991  
Dates: 


Number:  Number 171  
Number of Pages:  9  
DOI:  CSRR171  
Institution:  University of Warwick  
Theses Department:  Department of Computer Science  
Status:  Not Peer Reviewed  
Publication Status:  Unpublished  
Publisher Statement:  M.S. Paterson and U. Zwick, “Shrinkage of de Morgan Formulae under Restriction”, <i>Random Structures and Algorithms</i> <b>4</b>, pp. 135150 (1993)  
Funder:  European Strategic Programme of Research and Development in Information Technology (ESPRIT)  
Grant number:  3075 (ESPRIT)  
Related URLs: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year