TY - GEN
T1 - ON INFORMATION FLOW AND SORTING
T2 - NEW UPPER AND LOWER BOUNDS FOR VLSI CIRCUITS.
AU - Cole, Richard
AU - Siegel, Alan
PY - 1985
Y1 - 1985
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0022188125&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022188125&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1985.39
DO - 10.1109/sfcs.1985.39
M3 - Conference contribution
AN - SCOPUS:0022188125
SN - 0818606444
SN - 9780818606441
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 208
EP - 221
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -