On the depth of randomly generated circuits

DOI10.1007/3-540-61680-2_57MaRDI QIDQ4595488zbMATH OpenOpenAlexFDO

Authors Tatsuie Tsukiji, Fatos Xhafa

Publication date 5 December 2017

Published in Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/96471

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1372652
• On the Expected Depth of Random Circuits
• An average-case depth hierarchy theorem for Boolean circuits
• Average circuit depth and average communication complexity
• Malign distributions for average case circuit complexity.

Cited in

(7)

• Depth properties of scaled attachment random recursive trees
• Bounded-depth circuits cannot sample good codes
• On martingale tail sums in affine two-color urn models with multiple drawings
• Archaeology of random recursive dags and Cooper-Frieze random networks
• The number of descendants in a random directed acyclic graph
• Generation of all randomizations using circuits
• Outputs in random \(f\)-ary recursive circuits

This page was built for publication: On the depth of randomly generated circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595488)