Communication complexity under product and nonproduct distributions

DOI10.1007/S00037-009-0285-1MaRDI QIDQ623504zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(13)

• A little advice can be very helpful
• The Communication Complexity of Non-signaling Distributions
• Sign-rank can increase under intersection
• Upper and lower bounds on the power of advice
• The communication complexity of interleaved group products
• The hardest halfspace
• Correlation in Hard Distributions in Communication Complexity
• Amortized Communication Complexity of Distributions
• Communication complexity of statistical distance
• Communication complexity of statistical distance
• Partition bound is quadratically tight for product distributions
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• Sign rank versus Vapnik-Chervonenkis dimension

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)