How Do Read-Once Formulae Shrink?

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 \Gamma ")=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(" ff n + "n 1=ff ) variables, where ff = log p 5\Gamma1 2 ' 3:27. This result is asymptotically the tightest possible. It improves a similar result obtained recently by Hastad, Razborov and Yao. 1 Introduction Obtaining non-trivial lower bounds on the complexity of Boolean functions is currently a very difficult task. Only a handful of methods yielding such lower bounds are currently known and even they work only in suitably restricted models. The current state of affairs in this respect is summerized in the books of Dunne [5] and Wegener [15] and the survey paper of Boppana and Sipser [2]. Many of the currently known methods for obtaining complexity l..