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

circuitcommunication complexityrandom graphtensor rank

Mathematics Subject Classification ID

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

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

(26)

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