Superconcentrators of depth 2
From MaRDI portal
Publication:1162816
DOI10.1016/0022-0000(82)90056-3zbMath0482.68061OpenAlexW2016579872MaRDI QIDQ1162816
Publication date: 1982
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(82)90056-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (13)
Communication in bounded depth circuits ⋮ Meanders and their applications in lower bounds arguments ⋮ Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements ⋮ Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates ⋮ Min-rank conjecture for log-depth circuits ⋮ On shifting networks ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ Lower bounds for matrix factorization ⋮ Representing \((0,1)\)-matrices by Boolean circuits ⋮ Lower bounds for matrix factorization ⋮ Extracting randomness: A survey and new constructions ⋮ A geometric construction of a superconcentrator of depth 2 ⋮ Superconcentrators of depths 2 and 3; odd levels help (rarely)
Cites Work
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Corrigendum to ``Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Graph-theoretic properties in computational complexity
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Superconcentrators
This page was built for publication: Superconcentrators of depth 2
