Please use this identifier to cite or link to this item:

On the expected depth of random circuits

Authors Arya, Sunil View this author's profile
Golin, Mordecai Jay View this author's profile
Mehlhorn, Kurt
Issue Date 1999
Source COMBINATORICS Probability & COMPUTING , v. 8, (3), 1999, MAY, p. 209-227
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.
ISSN 0963-5483
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
circuits.pdf 303851 B Adobe PDF