Probabilistic communication complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- Computational Complexity of Probabilistic Turing Machines
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- 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\)
Cited in
(64)- Correlation in Hard Distributions in Communication Complexity
- On multiparty communication with large versus unbounded error
- The hardest halfspace
- The Communication Complexity of Non-signaling Distributions
- Average and randomized communication complexity
- Bounds on tradeoffs between randomness and communication complexity
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- scientific article; zbMATH DE number 7092118 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Lower bounds for one-way probabilistic communication complexity
- On the hardness of approximate and exact (bichromatic) maximum inner product
- On the power of statistical zero knowledge
- Linear algebraic methods in communication complexity
- A characterization of average case communication complexity
- Unbounded-Error Classical and Quantum Communication Complexity
- Results on communication complexity classes
- Unbounded-error quantum query complexity
- Communication complexity of multi-processor systems
- scientific article; zbMATH DE number 7559066 (Why is no real title available?)
- Rectangles are nonnegative juntas
- Amortized communication complexity of an equality predicate
- The unbounded-error communication complexity of symmetric functions
- Upper bounds on communication in terms of approximate rank
- A combinatorial approach to complexity
- Communication complexity and combinatorial lattice theory
- Essential sign change numbers of full sign pattern matrices
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
- scientific article; zbMATH DE number 176553 (Why is no real title available?)
- A short list of equalities induces large sign-rank
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Fooling pairs in randomized communication complexity
- Threshold circuit lower bounds on cryptographic functions
- Matrix and tensor rigidity and \(L_p\)-approximation
- The landscape of communication complexity classes
- Sign rank versus Vapnik-Chervonenkis dimension
- Sign-rank can increase under intersection
- On the communication complexity of distributed algebraic computation
- Minimum vertex cover, distributed decision-making, and communication complexity
- Different Modes of Communication
- Probabilistic communication complexity over the reals
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Complexity measures of sign matrices
- Lower bounds for the majority communication complexity of various graph accessibility problems
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- scientific article; zbMATH DE number 2081103 (Why is no real title available?)
- Lower bounds for approximating graph parameters via communication complexity
- scientific article; zbMATH DE number 6696541 (Why is no real title available?)
- Sign rank vs discrepancy
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Relations between communication complexity classes
- Tribes is hard in the message passing model
- A linear lower bound on the unbounded error probabilistic communication complexity.
- The communication complexity of pointer chasing: applications of entropy and sampling
- Rational realization of the minimum ranks of nonnegative sign pattern matrices.
- Polynomial threshold functions and Boolean threshold circuits
- Communication complexity of set-disjointness for all probabilities
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Upper bounds on communication in terms of approximate rank
- Approximate Degree in Classical and Quantum Computing
- Lower bounds on communication complexity
- scientific article; zbMATH DE number 4147508 (Why is no real title available?)
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- Learning complexity vs communication complexity
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)
