Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Seminar tomorrow with Arkadev Chattapadhyay

Gregory Valiant gvaliant at
Thu Oct 8 14:41:27 PDT 2015

Just a reminder that the theory seminar will be at 4pm per usual, with
Arkadev Chattapadhyay telling us about how graph topology matters for
communication problems on graphs.


On Wed, Oct 7, 2015 at 11:33 AM, Gregory Valiant
<gvaliant at> wrote:
> Hi Everyone,
> 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
> Abstract:
> 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
> communication cost.
> 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
> 1-median costs.
> 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 mailing list