Probabilistic communication complexity
Communication is a bottleneck in many distributed computations. In VLSI, communication constraints dictate lower bounds on the performance of chips. The two-processor information transfer model measures the communication requirements to compute functions. We study the unbounded error probabilistic version of this model. Because of its weak notion of correct output, we believe that this model measures the ``intrinsic communication complexity of functions. We present exact characterizations of the unbounded error communication complexity in terms of arrangements of hyperplanes and approximations of matrices. These characterizations establish the connection with certain classical problems in combinatorial geometry which are concerned with the configurations of points in d- dimensional real space. With the help of these characterizations, we obtain some upper and lower bounds on communication complexity. The upper bounds which we obtained for the functions - equality and verifications of Hamming distance - are considerably better than their counterparts in the deterministic, the nondeterministic, and the bounded error probabilistic models. We also exhibit a function which has log n complexity. We present a counting argument to show that most functions have linear complexity. Further, we apply the logarithmic lower bound on communication complexity to obtain an \(\Omega\) (n log n) bound on the time of 1-tape unbounded error probabilistic Turing machines. We believe that this is the first nontrivial lower bound obtained for such machines.
- Computational Complexity of Probabilistic Turing Machines
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- Information Transfer in Distributed Computing with Applications to VLSI
- Lopsided sets and orthant-intersection by convex sets
- On the Betti Numbers of Real Varieties
- Oriented matroids
- Partition of Space
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- Lower bounds on communication complexity
- Communication complexity of multi-processor systems
- The linear-array conjecture in communication complexity is false
- Results on communication complexity classes
- A combinatorial approach to complexity
- Communication complexity and combinatorial lattice theory
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- The landscape of communication complexity classes
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Fourier analysis for probabilistic communication complexity
- The hardest halfspace
- Upper bounds on communication in terms of approximate rank
- Matrix and tensor rigidity and L_p-approximation
- Probabilistic communication complexity over the reals
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- The unbounded-error communication complexity of symmetric functions
- Threshold circuit lower bounds on cryptographic functions
- Polynomial threshold functions and Boolean threshold circuits
- Communication complexity of set-disjointness for all probabilities
- Rational realization of the minimum ranks of nonnegative sign pattern matrices.
- Fooling pairs in randomized communication complexity
- Tribes is hard in the message passing model
- scientific article; zbMATH DE number 6696541 (Why is no real title available?)
- Essential sign change numbers of full sign pattern matrices
- Different Modes of Communication
- The Communication Complexity of Non-signaling Distributions
- scientific article; zbMATH DE number 4147508 (Why is no real title available?)
- Average and randomized communication complexity
- Learning complexity vs communication complexity
- scientific article; zbMATH DE number 176553 (Why is no real title available?)
- Linear algebraic methods in communication complexity
- scientific article; zbMATH DE number 1256713 (Why is no real title available?)
- On the communication complexity of distributed algebraic computation
- scientific article; zbMATH DE number 2081103 (Why is no real title available?)
- Sign rank versus Vapnik-Chervonenkis dimension
- On multiparty communication with large versus unbounded error
- Lower bounds for one-way probabilistic communication complexity
- Lower bounds for the majority communication complexity of various graph accessibility problems
- Amortized communication complexity of an equality predicate
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
- Lower bounds for approximating graph parameters via communication complexity
- Approximate Degree in Classical and Quantum Computing
- A short list of equalities induces large sign-rank
- Classical algorithms from quantum and Arthur-Merlin communication protocols
- Sign-rank can increase under intersection
- Sign rank vs discrepancy
- On the power of statistical zero knowledge
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- On the hardness of approximate and exact (bichromatic) maximum inner product
- The large-error approximate degree of \(\mathrm{AC}^0\)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- scientific article; zbMATH DE number 7092118 (Why is no real title available?)
- Correlation in Hard Distributions in Communication Complexity
- Unbounded-Error Classical and Quantum Communication Complexity
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Rectangles are nonnegative juntas
- LATIN 2004: Theoretical Informatics
- Minimum vertex cover, distributed decision-making, and communication complexity
- Unbounded-error quantum query complexity
- The communication complexity of pointer chasing: applications of entropy and sampling
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Upper bounds on communication in terms of approximate rank
- Bounds on tradeoffs between randomness and communication complexity
- Separation of the factorization norm and randomized communication complexity
- Communication complexity and discrepancy of halfplanes
- Randomized communication and implicit graph representations
- Communication memento: memoryless communication complexity
- Better boosting of communication oracles, or not
- Using oriented matroids to bound the monotone rank of a matrix
- Relations between communication complexity classes
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- A characterization of average case communication complexity
- Complexity measures of sign matrices
This page was built for publication: Probabilistic communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579927)
