# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### On the Expected Depth of Random Circuits

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arya, S., Golin, M. J., & Mehlhorn, K. (1999). On the Expected Depth of Random
Circuits.* Combinatorics, Probability and Computing,* *8*,
209-228.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3576-2

##### Abstract

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 ln n.