Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the depth of randomly generated circuits

Autor
Tsukiji, T.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
Lecture notes in computer science
Data de publicació
1996
Volum
1136
Pàgina inicial
208
Pàgina final
220
DOI
https://doi.org/10.1007/3-540-61680-2_57 Obrir en finestra nova
URL
https://link.springer.com/chapter/10.1007/3-540-61680-2_57 Obrir en finestra nova
Resum
This research is motivated by the Circuit Value Problem; this problem is well known to be inherently sequential. We consider Boolean circuits with descriptions length d that consist of gates with a fixed fan-in f and a constant number of inputs. Assuming uniform distribution of descriptions, we show that such a circuit has expected depth O(log d). This improves on the best known result. More precisely, we prove for circuits of size n their depth is asymptotically ef ln n with extremely high prob...
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants