de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

On the Expected Depth of Random Circuits

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44034

Arya,  Sunil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44509

Golin,  Mordecai J.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte 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, 209-228.


Zitierlink: http://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.