LCS Publication Details
Publication Title: LOWER BOUNDS FOR RECOGNIZING SMALL CLIQUES ON CRCW PRAM'S
Publication Author: Beame, Paul
Additional Authors:
LCS Document Number: MIT-LCS-TM-336
Publication Date: 8-1-1987
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
We show that any CRCW PRAM which recognizes k-cliques in n-node graphs in time T requires at least n (k)/T2) processors independent of its memory size. As a corollary we obtain essentially the same trade-off for unbounded fan-in circuits. We also demonstrate a similar but weaker trade-off for the memory size of CRCW PRAM's solving this problem independent of number of processors. These bounds also answer an open question posed in [Ly1],i.e. they show that constant-depth circuits for recognizing k-cliques in n-node graphs require size n(k).
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.