Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates

DOI10.1007/978-3-540-79709-8_15zbMath1142.68364OpenAlexW1566003175MaRDI QIDQ3503631

D. Yu. Cherukhin

Publication date: 5 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79709-8_15

zbMATH Keywords

complexitylower bounddepthcircuitBoolean functioncyclic convolution

Mathematics Subject Classification ID

Related Items (1)

Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements

Cites Work

• Unnamed Item
• Unnamed Item
• On shifting networks
• Entropy of operators or why matrix multiplication is hard for depth-two circuits
• Superconcentrators of depth 2
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• Communication in bounded depth circuits
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators

This page was built for publication: Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates