Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Zeitschriftenartikel

On the Expected Depth of Random Circuits

MPG-Autoren
/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;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-3576-2
Zusammenfassung
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.