Arya, Sunil; Golin, Mordecai J.; Mehlhorn, Kurt On the expected depth of random circuits. (English) Zbl 0941.68001 Comb. Probab. Comput. 8, No. 3, 209-228 (1999). Summary: We analyze 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\dots f\ln n\). Cited in 8 Documents MSC: 68M07 Mathematical problems of computer architecture 05C05 Trees 05C80 Random graphs (graph-theoretic aspects) Keywords:random circuits PDFBibTeX XMLCite \textit{S. Arya} et al., Comb. Probab. Comput. 8, No. 3, 209--228 (1999; Zbl 0941.68001) Full Text: DOI