Communication complexity under product and nonproduct distributions

DOI10.1007/s00037-009-0285-1zbMath1204.68102OpenAlexW2176265082MaRDI QIDQ623504

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

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

Related Items (5)

Sign rank versus Vapnik-Chervonenkis dimension ⋮ The hardest halfspace ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Unnamed Item

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