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 language | English |
---|---|
Title of host publication | Proceedings of the Twelfth Annual Symposium on Discrete Algorithms |
Publisher | ACM-SIAM |
Pages | 702--708 |
Publication status | Published - Jan 2001 |
Event | Twelfth Annual Symposium on Discrete Algorithms - Washington, DC, United States Duration: 7 Jan 2001 → … |
Conference
Conference | Twelfth Annual Symposium on Discrete Algorithms |
---|---|
Abbreviated title | SODA'2001 |
Country/Territory | United States |
City | Washington, DC |
Period | 7/01/2001 → … |