Title:
|
On the expected depth of boolean circuits
|
Author:
|
Díaz Cort, Josep; Serna Iglesias, María José; Spirakis, Paul George; Torán Romero, Jacobo
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
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. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Programació -Boolean circuit depth -Uniform model -NC -Monotone circuit value |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|