Which formulae shrink under random restrictions?

Hana Chockler, Uri Zwick

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

1 Citation (Scopus)

Abstract

We show that the shrinkage exponent, under random restrictions, of formulae over a finite complete basis B of Boolean functions is strictly greater than 1 if and only if all the functions in B are monotone increasing or monotone decreasing in each one of their variables. As a consequence, we get non-linear lower bounds on the formula complexity of the parity function over any basis composed only of monotone increasing or decreasing functions.
Original languageEnglish
Title of host publicationProceedings of the Twelfth Annual Symposium on Discrete Algorithms
PublisherACM-SIAM
Pages702--708
Publication statusPublished - Jan 2001
EventTwelfth Annual Symposium on Discrete Algorithms - Washington, DC, United States
Duration: 7 Jan 2001 → …

Conference

ConferenceTwelfth Annual Symposium on Discrete Algorithms
Abbreviated titleSODA'2001
Country/TerritoryUnited States
CityWashington, DC
Period7/01/2001 → …

Fingerprint

Dive into the research topics of 'Which formulae shrink under random restrictions?'. Together they form a unique fingerprint.

Cite this