On the Expected Depth of Random Circuits

Arya, Sunil; Golin, Mordecai J.; Mehlhorn, Kurt

doi:10.1017/S096354839900382X

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

On the Expected Depth of Random Circuits

MPS-Authors

/persons/resource/persons44034

Arya, Sunil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44509

Golin, Mordecai J.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

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(3), 209-228. doi:10.1017/S096354839900382X.

Cite as: https://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.