Hostname: page-component-8448b6f56d-wq2xx Total loading time: 0 Render date: 2024-04-19T21:09:37.093Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Expected Depth of Random Circuits

Published online by Cambridge University Press:  01 May 1999

SUNIL ARYA ,
MORDECAI J. GOLIN  and
KURT MEHLHORN
SUNIL ARYA
Affiliation:
Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong (e-mail: arya@cs.ust.hk)
MORDECAI J. GOLIN
Affiliation:
Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong (e-mail: golin@cs.ust.hk)
KURT MEHLHORN
Affiliation:
Max-Planck-Institut für Informatik, D-66123 Saarbrücken, Germany (e-mail: mehlhorn@mpi-sb.mpg.de)
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 3 , May 1999 , pp. 209 - 228
Copyright
1999 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)