Article contents
How Do Read-Once Formulae Shrink?
Published online by Cambridge University Press: 12 September 2008
Abstract
Let f be a de Morgan read-once function of n variables. Let fε be the random restriction obtained by independently assigning to each variable of f, the value 0 with probability (1 -ε)/2, the value 1 with the same probability, and leaving it unassigned with probability ε. We show that fε depends, on the average, on only O(εαn + εn1/α) variables, where . This result is asymptotically the tightest possible. It improves a similar result obtained recently by Håstad, Razborov and Yao.
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1994
References
- 5
- Cited by