Communication complexity
From MaRDI portal
Suppose that a language \(L\subseteq \{0,1\}^*\) must be recognized by two distant computers. Each computer receives half of the input bits, and the computation proceeds using some protocol for communication between the two computers (obviously, most interesting languages cannot be recognized with any communication). The minimum number of bits that has to be exchanged in order to successfully recognize \(L\cap \{0,1\}^{2n}\), minimized over all partitions of the input bits into two equal parts, and considered as a function of n, is called the communication complexity of L. In this paper we prove several results concerning this complexity measure.
Recommendations
Cites work
Cited in
(56)- On the P versus NP intersected with co-NP question in communication complexity
- The advantages of a new approach to defining the communication complexity for VLSI
- Communication complexity of multi-processor systems
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- Results on communication complexity classes
- Lower bounds on the area complexity of Boolean circuits
- Communication complexity of two decision problems
- Trade-offs between communication and space
- Lower bounds on the multiparty communication complexity
- Communication complexity and combinatorial lattice theory
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- On the power of randomized multicounter machines
- Complete classifications for the communication complexity of regular languages
- ``Global graph problems tend to be intractable
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- On multi-partition communication complexity
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- Probabilistic communication complexity over the reals
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Individual communication complexity
- Computing (and Life) Is All about Tradeoffs
- Space-bounded communication complexity
- Universal semantic communication
- Quantifying communication in synchronized languages
- scientific article; zbMATH DE number 3881884 (Why is no real title available?)
- scientific article; zbMATH DE number 3872716 (Why is no real title available?)
- Superlinear lower bounds for multipass graph processing
- Quantifying communication in synchronized languages
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- scientific article; zbMATH DE number 4147508 (Why is no real title available?)
- On limitations of transformations between combinatorial problems
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 1962802 (Why is no real title available?)
- scientific article; zbMATH DE number 2134904 (Why is no real title available?)
- scientific article; zbMATH DE number 1405691 (Why is no real title available?)
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Half-duplex communication complexity
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- A nonlinear lower bound on the practical combinational complexity
- On the complexity of communication complexity
- Communication Complexity
- STACS 2004
- One-way multiparty communication lower bound for pointer jumping with applications
- Best-order streaming model
- Automata, Languages and Programming
- The communication complexity of addition
- The communication complexity of pointer chasing
- On the power of Las Vegas II: Two-way finite automata
- On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
- An information statistics approach to data stream and communication complexity
- Paradigms for Unconditional Pseudorandom Generators
- A nonlinear lower bound on the practical combinational complexity
- Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
- A VLSI circuit model accounting for wire delay
- Pointer chasing with unlimited interaction
- Communication complexity of PRAMs
This page was built for publication: Communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069701)
