On shifting networks

DOI10.1016/0304-3975(93)90332-NzbMATH Open0777.94025MaRDI QIDQ685361FDOQ685361

Authors: Pavel Pudlák, Petr Savický 

Publication date: 17 October 1993

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

Recommendations

• 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
• A Boolean function requiring 3n network size
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• scientific article; zbMATH DE number 4104386

zbMATH Keywords

Boolean functionsnonlinear lower bounds on Boolean circuits

Mathematics Subject Classification ID

Cites Work

• Shifting Graphs and Their Applications
• Superconcentrators of depth 2
• Rearrangeable Networks with Limited Depth
• Title not available (Why is that?)

Cited In (10)

• Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
• On the complexity of a cyclic shift of a set of real numbers
• Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
• On complexity of linear operators on the class of circuits of depth 2
• Communication in bounded depth circuits
• The complexity of depth-two information networks
• Representing \((0,1)\)-matrices by Boolean circuits
• Min-rank conjecture for log-depth circuits
• Entropy of operators or why matrix multiplication is hard for depth-two circuits
• Computer Science Logic

This page was built for publication: On shifting networks

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