ISSN:
1439-6912
Keywords:
AMS Subject Classification (1991) Classes: 68Q15, 68Q25, 68R99
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
, 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- ≠ monotone- . 3. More generally: For any integer function D(n), up to (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- from monotone- 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 . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-clique function, with , 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004930050062
Permalink
