Boolean Circuits, Tensor Ranks, and Communication Complexity

DOI10.1137/S0097539794264809zbMATH Open0870.68068OpenAlexW1974827405MaRDI QIDQ4337651FDOQ4337651

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

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

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)

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
• Unexpected upper bounds on the complexity of some communication games
• The complexity of depth-two information networks
• 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
• Simultaneous multiparty communication protocols for composed functions
• Hadamard tensors and lower bounds on multiparty communication complexity
• On minrank and the Lovász theta-function
• Topological bounds on the dimension of orthogonal representations of graphs
• Min-rank conjecture for log-depth circuits
• On shifting networks
• 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)