Loading...
Loading...

Go to the content (press return)

On the expected depth of boolean circuits

Author
Diaz, J.; Serna, M.; Spirakis, P.G.; Toran, J.
Type of activity
Report
Date
1994-02
Code
LSI-94-38-R
Repository
http://hdl.handle.net/2117/97214 Open in new window
Abstract
In this paper we analyze the expected depth of a circuit randomly generated from a uniform model. We show that the expected depth of such circuits is polylogarithmic in the number of gates. This result allows us to place the monotone circuit value problem in average NC.
Citation
Diaz, J., Serna, M., Spirakis, P.G., Toran, J. "On the expected depth of boolean circuits". 1994.
Keywords
Boolean circuit depth, Monotone circuit value, NC, Uniform model
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments