Please use this identifier to cite or link to this item: doi:10.22028/D291-26447
Title: Four results on the complexity of VLSI computations
Author(s): Lengauer, Thomas
Mehlhorn, Kurt
Language: English
Year of Publication: 1983
Free key words: complexity theory
lower bounds
VLSI models
switching energy
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: We present four results on the complexity of VLSI computations: a) We further justify the Boolean circuit model [Vu, Sa, LS] by showing that it is able to model multi-directional VLSI devices (e.g. pass transistors, pre-charged bus drivers). b) We prove a general cutting theorem for compact regions in R^{d} (d\geq2) that allows us to drop the convexity assumption in lower bound proofs based on the crossing sequence argument. c) We exhibit an \Omega(n^{1/3}) asymptotically tight lower bound on the area of strongly where-oblivious chips for transitive functions. d) We prove a lower bound on the switching energy needed for computing transitive functions.
Link to this record: urn:nbn:de:bsz:291-scidok-51384
Series name: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Series volume: 1983/01
Date of registration: 3-Apr-2013
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1983_01.pdf12,69 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.