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