Superconcentrators of depths 2 and 3; odd levels help (rarely)

DOI10.1016/S0022-0000(05)80027-3zbMath0802.68095OpenAlexW2049815987MaRDI QIDQ1318476

Pavel Pudlák, Noga Alon

Publication date: 27 April 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80027-3

zbMATH Keywords

directed acyclic graphsuperconcentrators

Mathematics Subject Classification ID

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

Related Items (11)

Communication in bounded depth circuits ⋮ Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors ⋮ 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 ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ On the minimum depth of circuits with linear number of wires encoding good codes ⋮ Lower bounds for matrix factorization ⋮ Representing \((0,1)\)-matrices by Boolean circuits ⋮ Lower bounds for matrix factorization ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

• Unnamed Item
• A geometric construction of a superconcentrator of depth 2
• Meanders and their applications in lower bounds arguments
• Superconcentrators of depth 2
• Communication in bounded depth circuits

This page was built for publication: Superconcentrators of depths 2 and 3; odd levels help (rarely)