@inproceedings{0abfdf523f554df2bb3f4d07c89ac715,
title = "On the area-time optimal design of l-selectors",
abstract = "We prove upper and lower bounds on the area-time complexity of the problem of selecting the l-th smallest of n k-bit integers. When chip area is restricted to Θ(n), our O (k logn)-time circuit is provably area-time optimal to within a factor of O (logn). We present several circuit constructions having area other than Θ(n), but these are typically a factor of O(1) from area-time optimality. The development of tight upper and lower bounds for l-selectors of nonlinear area is thus an open problem.",
author = "Thompson, {Clark D.} and Hiroto Yasuura",
note = "Funding Information: This work was supported in part by the National Science Foundation, through its Computer Engineering program, under grant DMC 84-06408. Funding Information: This work waa supported in part by the National Science Foundation, through it.? Computer Engineering program, under grant DMC 84-06408. Publisher Copyright: {\textcopyright} 1985 IEEE.; 19th Asilomar Conference on Circuits, Systems and Computers, ACSSC 1985 ; Conference date: 06-11-1985 Through 08-11-1985",
year = "1985",
doi = "10.1109/ACSSC.1985.671482",
language = "English",
series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",
publisher = "IEEE Computer Society",
pages = "365--368",
editor = "Kirk, {Donald E.}",
booktitle = "Conference Record - 19th Asilomar Conference on Circuits, Systems and Computers, ACSSC 1985",
address = "United States",
}