Communication complexity
From MaRDI portal
Publication:1069701
DOI10.1016/0022-0000(84)90069-2zbMATH Open0584.68064OpenAlexW4211003473MaRDI QIDQ1069701FDOQ1069701
Christos Papadimitriou, Michael Sipser
Publication date: 1984
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(84)90069-2
Recommendations
Cites Work
Cited In (51)
- On the complexity of communication complexity
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- STACS 2004
- One-way multiparty communication lower bound for pointer jumping with applications
- Best-order streaming model
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- Lower bounds on the area complexity of Boolean circuits
- Title not available (Why is that?)
- The advantages of a new approach to defining the communication complexity for VLSI
- Title not available (Why is that?)
- Paradigms for Unconditional Pseudorandom Generators
- Space-bounded communication complexity
- Results on communication complexity classes
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Communication complexity of multi-processor systems
- On the power of Las Vegas II: Two-way finite automata
- ``Global graph problems tend to be intractable
- Communication complexity and combinatorial lattice theory
- Title not available (Why is that?)
- On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
- An information statistics approach to data stream and communication complexity
- On the power of randomized multicounter machines
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Quantifying Communication in Synchronized Languages
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Probabilistic communication complexity over the reals
- Communication Complexity
- Individual communication complexity
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Communication complexity of PRAMs
- Title not available (Why is that?)
- Superlinear lower bounds for multipass graph processing
- Quantifying communication in synchronized languages
- On the P versus NP intersected with co-NP question in communication complexity
- The communication complexity of addition
- The communication complexity of pointer chasing
- Communication complexity of two decision problems
- Trade-offs between communication and space
- Computing (and Life) Is All about Tradeoffs
- Title not available (Why is that?)
- Automata, Languages and Programming
- Lower bounds on the multiparty communication complexity
- Title not available (Why is that?)
- On limitations of transformations between combinatorial problems
- Title not available (Why is that?)
- On multi-partition communication complexity
- Title not available (Why is that?)
- A nonlinear lower bound on the practical combinational complexity
- A nonlinear lower bound on the practical combinational complexity
- Complete classifications for the communication complexity of regular languages
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)
