Boolean Circuits, Tensor Ranks, and Communication Complexity
From MaRDI portal
Publication:4337651
DOI10.1137/S0097539794264809zbMath0870.68068OpenAlexW1974827405MaRDI QIDQ4337651
Jiří Sgall, Pavel Pudlák, Vojtěch Rödl
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
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)
Related Items (23)
On complexity of linear operators on the class of circuits of depth 2 ⋮ Upper bound on the communication complexity of private information retrieval ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ The function-inversion problem: barriers and opportunities ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ Min-rank conjecture for log-depth circuits ⋮ Matrix rigidity ⋮ Matrix rank and communication complexity ⋮ Unexpected upper bounds on the complexity of some communication games ⋮ The minrank of random graphs ⋮ Interleaved Group Products ⋮ Some structural properties of low-rank matrices related to computational complexity ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ The complexity of depth-two information networks ⋮ Private information retrieval with sublinear online time ⋮ Topological bounds on the dimension of orthogonal representations of graphs ⋮ Representing \((0,1)\)-matrices by Boolean circuits ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
This page was built for publication: Boolean Circuits, Tensor Ranks, and Communication Complexity
