A Tight \Omega(log log n)-Bound on the time for Parallel RAM's to Compute Nondegenerated Boolean Function

Abstract.  A function f: {0,1}n \to {0,1} is said to depend on dimension i iff there exists an input vector x such that f(x) differs from f(xi), where xi agrees with x in every dimension except i. In this case x is said to be critical for f with respect to i. Function f is called nondegenerated iff it depends on all n dimensions. The main result of this paper is that for each nondegenerated function f: {0,1}n \to {0,1} there exists an input vector x which is critical with respect to at least \Omega(log n) dimensions. A function achieving this bound is presented. Together with earlier results from Cook and Dwork (``Proceeding, 14th ACM Symp. on Theory of Computing'', 1982) and Reischuk (IBM Research Report, No. RJ 3431, 1982) it can be concluded that a parallel RAM requires at least \Omega(log log n) steps to compute f.