Communication in bounded depth circuits

DOI10.1007/BF01215351MaRDI QIDQ1330798zbMATH OpenOpenAlexFDO

Authors Pavel Pudlák

Publication date 11 August 1994

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01215351

zbMATH Keywords

algebraic complexitycomplexity of communication networkinformation processinginformation transfer

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Matrix rigidity

Cites work

• On shifting networks
• Rearrangeable Networks with Limited Depth
• Superconcentrators of depth 2
• Superconcentrators of depths 2 and 3; odd levels help (rarely)

Cited in

(32)

• Representing \((0,1)\)-matrices by Boolean circuits
• Improved lower bounds on the rigidity of Hadamard matrices
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• Some combinatorial-algebraic problems from complexity theory
• Algebraic techniques in communication complexity
• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Affine projections of symmetric polynomials.
• Bounded depth broadcasting
• Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors
• Matrix rigidity
• Matrix rank and communication complexity
• Lower bounds for matrix factorization
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
• A remark on matrix rigidity
• On complexity of linear operators on the class of circuits of depth 2
• 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
• scientific article; zbMATH DE number 4051664 (Why is no real title available?)
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• On a theorem of Razborov
• Lower bounds for matrix factorization
• A super-quadratic lower bound for depth four arithmetic circuits
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Circuit complexity of regular languages
• Min-rank conjecture for log-depth circuits
• On the minimum depth of circuits with linear number of wires encoding good codes
• Efficient construction of rigid matrices using an NP oracle
• Kronecker products, low-depth circuits, and matrix rigidity
• High girth augmented trees are huge
• Entropy of operators or why matrix multiplication is hard for depth-two circuits

This page was built for publication: Communication in bounded depth circuits

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