On the expected depth of boolean circuits

Consultar RECERCAT

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/97214

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Díaz Cort, Josep
dc.contributor.author	Serna Iglesias, María José
dc.contributor.author	Spirakis, Paul George
dc.contributor.author	Torán Romero, Jacobo
dc.date	1994-02
dc.identifier.citation	Diaz, J., Serna, M., Spirakis, P.G., Toran, J. "On the expected depth of boolean circuits". 1994.
dc.identifier.uri	http://hdl.handle.net/2117/97214
dc.language.iso	eng
dc.relation	LSI-94-38-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Programació
dc.subject	Boolean circuit depth
dc.subject	Uniform model
dc.subject	NC
dc.subject	Monotone circuit value
dc.title	On the expected depth of boolean circuits
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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.

Díaz Cort, Josep; Serna Iglesias, María José; Torán Romero, Jacobo

Díaz Cort, Josep; Serna Iglesias, María José; Spirakis, Paul George

Díaz Cort, Josep; Serna Iglesias, María José; Spirakis, Paul George

Díaz Cort, Josep; Serna Iglesias, María José; Spirakis, Paul George

Díaz Cort, Josep; Sanwalani, Vishal; Serna Iglesias, María José; Spirakis, Paul George

Coordinació

Patrocini