Communication complexity under product and nonproduct distributions

DOI10.1007/S00037-009-0285-1zbMATH Open1204.68102OpenAlexW2176265082MaRDI QIDQ623504FDOQ623504

Authors: Alexander A. Sherstov 

Publication date: 7 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0285-1

Recommendations

• scientific article; zbMATH DE number 1769898
• Exponential separation of information and communication for Boolean functions
• Partition bound is quadratically tight for product distributions
• Correlation in Hard Distributions in Communication Complexity
• Communication complexity of statistical distance

zbMATH Keywords

product and nonproduct distributionsrandomized and distributional communication complexityYao's minimax principle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (9)

• The Communication Complexity of Non-signaling Distributions
• The hardest halfspace
• Title not available (Why is that?)
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• The communication complexity of interleaved group products
• Sign rank versus Vapnik-Chervonenkis dimension
• Upper and lower bounds on the power of advice
• Amortized Communication Complexity of Distributions
• Correlation in Hard Distributions in Communication Complexity

This page was built for publication: Communication complexity under product and nonproduct distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623504)