Size bounds for superconcentrators

DOI10.1016/0304-3975(83)90105-6MaRDI QIDQ1170885zbMATH OpenOpenAlexFDO

Authors 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

directed acyclic graphdiscrete Fourier transform of prime order and cyclic convolutionfast algorithms

Mathematics Subject Classification ID

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

Cites work

• A note on time-space tradeoffs for computing continuous functions
• A Permutation Network
• Generalized Connection Networks for Parallel Processor Intercommunication
• Generalized Connectors
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3526016 (Why is no real title available?)
• scientific article; zbMATH DE number 3566171 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 3225079 (Why is no real title available?)
• scientific article; zbMATH DE number 3363674 (Why is no real title available?)
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On Computing the Discrete Fourier Transform
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• On rearrangeable and non-blocking switching networks
• On the multiplicative complexity of the discrete Fourier transform
• Superconcentrators
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(1)

• Communication lower bounds and optimal algorithms for numerical linear algebra

This page was built for publication: Size bounds for superconcentrators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1170885)