TY - JOUR
T1 - Separation of the monotone NC hierarchy
AU - Raz, Ran
AU - McKenzie, Pierre
N1 - Funding Information:
Mathematics Subject Classi cation (1991): 68Q15, 68Q25, 68R99 * Work supported by an American{Israeli BSF grant 95-00238. y Work supported by the NSERC of Canada and by the FCAR du Quebec.
PY - 1999
Y1 - 1999
N2 - We prove tight lower bounds, of up to n∈, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-NCi ≠ monotone-NCi+1. 3. More generally: For any integer function D(n), up to n∈ (for some ∈ > 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 circuits of depth less than Const · D(n) (for some constant Const). Only a separation of monotone-NC1 from monotone-NC2 was previously known. Our argument is more general: we define a new class of communication complexity 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 Ω(log2 n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-cliqne function, with k≤n∈, we get a tight lower bound of Ω(k log n). This lower bound was previously known for k ≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known.
AB - We prove tight lower bounds, of up to n∈, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-NCi ≠ monotone-NCi+1. 3. More generally: For any integer function D(n), up to n∈ (for some ∈ > 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 circuits of depth less than Const · D(n) (for some constant Const). Only a separation of monotone-NC1 from monotone-NC2 was previously known. Our argument is more general: we define a new class of communication complexity 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 Ω(log2 n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-cliqne function, with k≤n∈, we get a tight lower bound of Ω(k log n). This lower bound was previously known for k ≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known.
UR - http://www.scopus.com/inward/record.url?scp=0000965494&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0000965494&partnerID=8YFLogxK
U2 - 10.1007/s004930050062
DO - 10.1007/s004930050062
M3 - Article
AN - SCOPUS:0000965494
SN - 0209-9683
VL - 19
SP - 403
EP - 435
JO - Combinatorica
JF - Combinatorica
IS - 3
ER -