<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-171

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

M.S. Paterson and U. Zwick, Shrinkage of de Morgan Formulae under Restriction (January 1, 1991).

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^{((5-sqrt(3))/2)}~=epsilon^1.63. (A de Morgan formula is a formula over the basis {/\, \/, ~}.) This improves a long-standing result of epsilon^1.5 by Subbotovskaya and a recent improvement to epsilon^{((21-sqrt(73))/8)}~=epsilon^1.55 by Nisan and Impagliazzo. The new exponent yields an increased lower bound of omega(n^{((7-sqrt(3))/2-O(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.

<%@ include file="cited.html" %>

M.S. Paterson and U. Zwick, "Shrinkage of de Morgan Formulae under Restriction", Random Structures and Algorithms 4, pp. 135-150 (1993)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>