ON INFORMATION FLOW AND SORTING: NEW UPPER AND LOWER BOUNDS FOR VLSI CIRCUITS.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This work comprises two parts: lower bounds and upper bounds in VLSI circuits. The upper bounds are for the sorting problem: the authors describe a large number of constructions for sorting N numbers in the range left bracket 0,M right bracket for the standard VLSI bit model. The lower bounds apply to a variety of problems. Two new techniques are presented for establishing lower bounds on the information flow in VLSI circuits.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages208-221
Number of pages14
ISBN (Print)0818606444, 9780818606441
DOIs
StatePublished - 1985

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'ON INFORMATION FLOW AND SORTING: NEW UPPER AND LOWER BOUNDS FOR VLSI CIRCUITS.'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., & Siegel, A. (1985). ON INFORMATION FLOW AND SORTING: NEW UPPER AND LOWER BOUNDS FOR VLSI CIRCUITS. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 208-221). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE. https://doi.org/10.1109/sfcs.1985.39