Communication in bounded depth circuits

DOI10.1007/BF01215351zbMath0819.68090OpenAlexW1590864168MaRDI QIDQ1330798

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 complexityinformation processinginformation transfercomplexity of communication network

Mathematics Subject Classification ID

Related Items (26)

Affine projections of symmetric polynomials. ⋮ A remark on matrix rigidity ⋮ Some combinatorial-algebraic problems from complexity theory ⋮ A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle ⋮ Algebraic techniques in communication complexity ⋮ On complexity of linear operators on the class of circuits of depth 2 ⋮ 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 ⋮ On a theorem of Razborov ⋮ Min-rank conjecture for log-depth circuits ⋮ Matrix rigidity ⋮ Matrix rank and communication complexity ⋮ Circuit complexity of regular languages ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ Lower bounds for matrix factorization ⋮ High girth augmented trees are huge ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On the rigidity of Vandermonde matrices ⋮ Improved lower bounds on the rigidity of Hadamard matrices ⋮ Representing \((0,1)\)-matrices by Boolean circuits ⋮ Lower bounds for matrix factorization ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity ⋮ Superconcentrators of depths 2 and 3; odd levels help (rarely) ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

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

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