Separation of the monotone NC hierarchy

We prove tight lower bounds, of up to n(epsilon), for the monotone depth of functions in monotone-P. As a result we achieve the separation of the foll owing classes. 1. monotone-NC not equal monotone-P. 2. For every i greater than or equal to 1, monotone-NCi not equal monotone- NCi+1. 3. More generally: For any integer function D(n), up to n(epsilon) (for som e epsilon > 0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circu its of depth less than Const D(n) (for some constant Const). Only a separation of monotone-NC1 from monotone-NC2 was previously known. O ur argument is more general: we define a new class of communication complex ity search problems, referred to below as DART games, and we prove a. tight lower bound for the communication complexity of every member of this class . As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1. For st-connectivity, we get a tight lower bound of Omega(log(2) n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate c orollary of our general result. 2. For the k-clique function, with k less than or equal to n(epsilon), we g et a tigltt lower bound of Omega(k log n). This lower bound was previously known for k less than or equal to log n [1]. For larger k, however, only a bound of Omega(k) was previously known.