1979/10/01 by Nicholas Pippenger · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Computer science #Interconnection Networks and Systems #Low-power high-performance VLSI design #Mathematical analysis #Mathematics #Space (punctuation) #Space time #Upper and lower bounds #VLSI and FPGA Design Techniques
paper · doi:10.1109/sfcs.1979.29
openalex publication_date 1979/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
It is well known that time bounds for machines correspond closely to size bounds for networks, and that space bounds correspond to depth bounds. It is not known whether simultaneous time and space bounds correspond to simultaneous size and depth bounds. It is shown here that simultaneous time and "reversal" bounds correspond to simultaneous size and depth bounds, and that simultaneous time and space bounds correspond to simultaneous size and "width" bounds.