Circuit size is nonlinear in depth
From MaRDI portal
Publication:1233426
DOI10.1016/0304-3975(76)90090-6zbMath0345.94026OpenAlexW2138170131MaRDI QIDQ1233426
Leslie G. Valiant, Michael S. Paterson
Publication date: 1976
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/46306/1/WRAP_Valiant_cs-rr-008.pdf
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ Rounds versus time for the two person pebble game ⋮ Weighted Boolean Formula Games ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ The size and depth of layered Boolean circuits ⋮ Parallelizing time with polynomial circuits ⋮ Rounds versus time for the two person pebble game ⋮ Speedups of deterministic machines by synchronous parallel machines
Cites Work
This page was built for publication: Circuit size is nonlinear in depth
