Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness

DOI10.4230/LIPIcs.STACS.2009.1846zbMath1236.68093OpenAlexW1557064786MaRDI QIDQ5390003

André Gronemeier

Publication date: 24 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_33d3.html

zbMATH Keywords

computational complexitycommunication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model, Communication Lower Bounds via Critical Block Sensitivity, Zero-information protocols and unambiguity in Arthur-Merlin communication, Certifying equality with limited interaction, Towards Optimal Moment Estimation in Streaming and Distributed Models, Towards Optimal Moment Estimation in Streaming and Distributed Models, Unnamed Item, Forty years of frequent items, Continuous Monitoring of l_p Norms in Data Streams, Partition arguments in multiparty communication complexity, Unnamed Item, Unnamed Item, Tradeoff lower lounds for stack machines, Information complexity of the AND function in the two-party and multi-party settings, The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model, Everywhere-Tight Information Cost Tradeoffs for Augmented Index, Connectivity and connected components in the number-in-hand computation model