Boolean Circuits, Tensor Ranks, and Communication Complexity

DOI10.1137/S0097539794264809MaRDI QIDQ4337651zbMATH OpenOpenAlexFDO

Authors Pavel Pudlák, Vojtěch Rödl, Jiří Sgall

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794264809

zbMATH Keywords

random graphcircuitcommunication complexitytensor rank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Communication complexity towards lower bounds on circuit depth
• Communication in bounded depth circuits
• scientific article; zbMATH DE number 4068270
• The ``log rank conjecture for modular communication complexity
• Lower bounds on threshold and related circuits via communication complexity

Cited in

(24)

• Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
• On minrank and forbidden subgraphs
• Upper bound on the communication complexity of private information retrieval
• 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
• Interleaved Group Products
• Matrix rank and communication complexity
• Private information retrieval with sublinear online time
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• The function-inversion problem: barriers and opportunities
• The complexity of depth-two information networks
• Unexpected upper bounds on the complexity of some communication games
• Representing \((0,1)\)-matrices by Boolean circuits
• Matrix rigidity
• Optimal collapsing protocol for multiparty pointer jumping
• Some structural properties of low-rank matrices related to computational complexity
• Hadamard tensors and lower bounds on multiparty communication complexity
• Simultaneous multiparty communication protocols for composed functions
• Min-rank conjecture for log-depth circuits
• On minrank and the Lovász theta-function
• On shifting networks
• Topological bounds on the dimension of orthogonal representations of graphs
• The minrank of random graphs
• Entropy of operators or why matrix multiplication is hard for depth-two circuits

This page was built for publication: Boolean Circuits, Tensor Ranks, and Communication Complexity

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