Size bounds for superconcentrators

DOI10.1016/0304-3975(83)90105-6zbMath0497.68022OpenAlexW2022300065MaRDI QIDQ1170885

G. Lev, Leslie G. Valiant

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90105-6

zbMATH Keywords

fast algorithmsdirected acyclic graphdiscrete Fourier transform of prime order and cyclic convolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Communication lower bounds and optimal algorithms for numerical linear algebra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• On rearrangeable and non-blocking switching networks
• On the multiplicative complexity of the discrete Fourier transform
• A note on time-space tradeoffs for computing continuous functions
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• Superconcentrators
• On Computing the Discrete Fourier Transform
• Generalized Connectors
• Generalized Connection Networks for Parallel Processor Intercommunication
• A Permutation Network
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

This page was built for publication: Size bounds for superconcentrators