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

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

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