English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 DetailsSummary
  On the Expected Depth of Random Circuits

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

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3576-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-414B-4
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Arya, Sunil1, Author           
Golin, Mordecai J.1, Author           
Mehlhorn, Kurt1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 1999
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 344701
Other: Local-ID: C1256428004B93B8-CBF5E4FADC0F4CBDC12571D80047CDEE-mehlhorn99y
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorics, Probability and Computing
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 8 Sequence Number: - Start / End Page: 209 - 228 Identifier: -