Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy

DOI10.1137/15M1007525zbMath1336.68105arXiv1107.2559OpenAlexW2568405002MaRDI QIDQ2796207

Elad Verbin, Qin Zhang, Jeff M. Phillips

Publication date: 23 March 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.2559

zbMATH Keywords

symmetrizationmultiparty communication complexitynumber-in-hand

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network protocols (68M12)

Related Items

Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model ⋮ Certifying equality with limited interaction ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ When distributed computation is communication expensive ⋮ Unnamed Item ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Unnamed Item ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ The Communication Complexity of Distributed epsilon-Approximations

Cites Work

• An information statistics approach to data stream and communication complexity
• Finding repeated elements
• On the distributional complexity of disjointness
• Lower bounds on the multiparty communication complexity
• The space complexity of approximating the frequency moments
• When distributed computation is communication expensive
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Optimal tracking of distributed heavy hitters and quantiles
• Approximate distributed top-\(k\) queries
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• How to compress interactive communication
• Towards polynomial lower bounds for dynamic problems
• Communication complexity of approximate matching in distributed graphs
• Approximating extent measures of points
• Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
• Functional Monitoring without Monotonicity
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Practical methods for shape fitting and kinetic data structures using core sets
• An Optimal Lower Bound for Distinct Elements in the Message Passing Model
• Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
• Continuous sampling from distributed streams
• Tight bounds for distributed functional monitoring
• Efficient top-K query calculation in distributed networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item