Probabilistic communication complexity
From MaRDI portal
Publication:579927
DOI10.1016/0022-0000(86)90046-2zbMath0625.68029OpenAlexW2008671796MaRDI QIDQ579927
Publication date: 1986
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(86)90046-2
combinatorial geometryHamming distanceVLSI1-tape unbounded error probabilistic Turing machinesdistributed computationstwo-processor information transfer modelunbounded error communication complexity
Related Items
A linear lower bound on the unbounded error probabilistic communication complexity. ⋮ Essential sign change numbers of full sign pattern matrices ⋮ Matrix and tensor rigidity and \(L_p\)-approximation ⋮ Lower bounds for one-way probabilistic communication complexity and their application to space complexity ⋮ Approximate Degree in Classical and Quantum Computing ⋮ The landscape of communication complexity classes ⋮ Communication complexity of multi-processor systems ⋮ Unnamed Item ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Linear algebraic methods in communication complexity ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Minimum vertex cover, distributed decision-making, and communication complexity ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Unbounded-error quantum query complexity ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Lower bounds for one-way probabilistic communication complexity ⋮ Learning Complexity vs Communication Complexity ⋮ The hardest halfspace ⋮ Results on communication complexity classes ⋮ Complexity measures of sign matrices ⋮ A combinatorial approach to complexity ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Threshold circuit lower bounds on cryptographic functions ⋮ Lower bounds for the majority communication complexity of various graph accessibility problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unnamed Item ⋮ Relations between communication complexity classes ⋮ Sign rank vs discrepancy ⋮ Rational realization of the minimum ranks of nonnegative sign pattern matrices ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication complexity and combinatorial lattice theory ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity ⋮ Upper bounds on communication in terms of approximate rank ⋮ On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
Cites Work
- Unnamed Item
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- Lopsided sets and orthant-intersection by convex sets
- Oriented matroids
- Information Transfer in Distributed Computing with Applications to VLSI
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- Computational Complexity of Probabilistic Turing Machines
- On the Betti Numbers of Real Varieties
- Partition of Space
