A tight Ω(loglog n)-bound on the time for parallel Ram's to compute nondegenerated boolean functions

Abstract

A function f: {0, 1}ⁿ → {0, 1} is said to depend on dimension i iff there exists an input vector x such that f(x) differs from f(xⁱ), where xⁱ agrees with x in every dimension except i. In this case x is said to be critical for f with respect to i. 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}ⁿ → {0, 1} there exists an input vector x which is critical with respect to at least Ω(log n) dimensions. A function achieving this bound is presented.

Together with earlier results from Cook,Dwork [2] and Reischuk [3] we can conclude that a parallel RAM requires at least Ω(loglog n) steps to compute f.