Search Mailing List Archives
[theory-seminar] Theory Seminar tomorrow with Arkadev Chattapadhyay
gvaliant at cs.stanford.edu
Wed Oct 7 11:33:16 PDT 2015
Arkadev will speak at tomorrow's theory seminar. Refreshments at
4pm, talk begins at 4:15. Hope to see you all there!
Title: Topology matters in communication
We study communication cost of computing functions when inputs are
distributed among k processors, each of which is located at one vertex
of a network/graph called a terminal. Every other node of the network
also has a processor, with no input. The communication is
point-to-point and the cost is the total number of bits exchanged by
the protocol, in the worst case, on all edges.
Our results show the effect of topology of the network on the total
We prove tight bounds for simple functions like Element-Distinctness
(ED), which depend on the 1-median of the graph. On the other hand, we
show that for a large class of natural functions like Set-Disjointness
the communication cost is essentially n times the cost of the optimal
Steiner tree connecting the terminals. Further, we show for natural
composed functions like ED∘XOR and XOR∘ED, the naive protocols
suggested by their definition is optimal for general networks.
Interestingly, the bounds for these functions depend on more involved
topological parameters that are a combination of Steiner tree and
To obtain our results, we use some tools like metric embeddings and
linear programming whose use in the context of communication
complexity is novel as far as we know.
(Based on joint works with Jaikumar Radhakrishnan and Atri Rudra)
More information about the theory-seminar