The critical complexity of graph properties (Q795503)

The critical complexity of a Boolean function \(f(x_ 1,...,x_ n)\) is \(c(f):=\max \{| \{i:\quad f(x)\neq f(x^ i)\}|:\quad x\in \{0,1\}^ n\},\) where \(x^ i\) is obtained by changing the i-th component of x. \textit{S. Cook} and \textit{C. Dwork} [Bounds on the time for parallel RAMs to compute simple functions, Proc. 14th ACM STOC, 231-233 (1982)] proved that log c(f) (in base \({1\over2}(5+\sqrt{21}))\) is a lower bound to the time needed by a parallel RAM to compute f. \textit{H.-U. Simon} [Lect. Notes Comput. Sci. 158, 439-444 (1983; Zbl 0523.68036)] gave a sharp \(\Omega\) (log n) bound for the critical complexity of nondegenerate Boolean functions. Here it is shown that if \(n=\left( \begin{matrix} m\\ 2\end{matrix} \right)\) and f is a nontrivial property of graphs on m vertices, then \(c(f)\geq \lfloor m/4\rfloor.\) (The property of containing an isolated point shows that the bound is sharp within a constant factor.) This implies an \(\Omega\) (log n) lower bound to the parallel complexity of graph properties.