Lower Bounds on Communication Complexity

Pavol Duris Zvi Galil Georg Schnitger

Published in: STOC (1984)

Keyphrases

lower bound
worst case
upper bound
objective function
branch and bound algorithm
communication systems
average case complexity
computational complexity
vc dimension
neural network
social networks
np hard
multi party
communication overhead
complexity measures