Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Arya, Sunil
Golin, Mordecai J.
Mehlhorn, Kurt

dblp
dblp
dblp

Not MPG Author(s):

??

BibTeX cite key*:

mehlhorn99

Title

Title*:

On the Expected Depth of Random Circuits

Journal

Journal Title*:

Combinatorics, Probability and Computing

Journal's URL:


Download URL
for the article:

http://journals.cambridge.org/download.php?file=%2FCPC%2FCPC8_03%2FS096354839900382Xa.pdf&code=9d8534371365cc445695a37a3d8fa71f

Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

8

Number:

209-228

Publishing Date:

1999

Pages*:

209-228

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{mehlhorn99,
AUTHOR = {Arya, Sunil and Golin, Mordecai J. and Mehlhorn, Kurt},
TITLE = {On the Expected Depth of Random Circuits},
JOURNAL = {Combinatorics, Probability and Computing},
YEAR = {1999},
NUMBER = {209-228},
VOLUME = {8},
PAGES = {209--228},
}


Entry last modified by Christine Kiesel, 08/28/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
08/28/2006 03:04:17 PM
Revision
0.



Editor
Christine Kiesel



Edit Date
28.08.2006 15:11:36



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section