The Library

Circuit size is nonlinear in depth

Tools

Valiant, L. G. and Paterson, Michael S. (1975) Circuit size is nonlinear in depth. Coventry, UK: Department of Computer Science..

Full text not available from this repository.

Abstract

Two fundamental complexity measures for a Boolean function $f$ are its circuit depth $d(f)$ and its circuit size $c(f)$. It is shown that $c\geq \frac{1}{4}d.log_2 d $ for all $f$.

Item Type: Report
Subjects: Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)
Divisions: Faculty of Science > Computer Science
Publisher: Department of Computer Science
Place of Publication: Coventry, UK
Date: September 1975
Identification Number: CS-RR-008
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
Related URLs:
URI: http://wrap.warwick.ac.uk/id/eprint/46306

Request changes to a record

Actions (login required)

View Item View Item