Semelectivity is not sufficient

DOI10.1016/0020-0190(91)90033-EzbMath0714.68047OpenAlexW2036305438MaRDI QIDQ751288

Pavol Ďuriš, Imrich Vrt'o

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90033-e

zbMATH Keywords

computational complexitylower boundarea complexityVLSI model

Mathematics Subject Classification ID

Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Where-oblivious is not sufficient
• Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformations
• Area-time lower-bound techniques with applications to sorting
• A minimum-area circuit for \(\ell\)-selection
• On problem transformability in VLSI
• Information Transfer in Distributed Computing with Applications to VLSI
• Minimum Storage Sorting Networks
• Information transfer and area-time tradeoffs for VLSI multiplication
• The Area-Time Complexity of Binary Multiplication