HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >

Please use this identifier to cite or link to this item:
Title: On the expected depth of random circuits
Authors: Arya, Sunil
Golin, Mordecai J.
Mehlhorn, Kurt
Keywords: Expected depth
Random circuits
Issue Date: 1998
Citation: Combinatorics, probability and computing, v. 8, 1999, p. 209-222
Abstract: In this paper 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 eflnn and from below by 2.04...flnn.
Appears in Collections:CSE Preprints

Files in This Item:

File Description SizeFormat
circuits.pdf296KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.