Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/468
On the expected depth of random circuits
Authors 
Arya, Sunil
Golin, Mordecai Jay Mehlhorn, Kurt 


Issue Date  1999  
Source  COMBINATORICS Probability & COMPUTING , v. 8, (3), 1999, MAY, p. 209227  
Summary  In this paper we analyse the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the previously added gates. The depth of the new gate is defined to be one more than the maximal depth of its input gates. We show that the expected depth of a random circuit with n gates is bounded from above by ef ln n and from below by 2.04...f In n.  
Subjects  
ISSN  09635483  
Language  English 

Format  Article  
Access 
View fulltext via Web of Science View fulltext via Scopus Files in this item:
