Search Mailing List Archives
[theory-seminar] Theory Seminar tomorrow with Arkadev Chattapadhyay
Gregory Valiant
gvaliant at cs.stanford.edu
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.
Cheers,
-greg
On Wed, Oct 7, 2015 at 11:33 AM, Gregory Valiant
<gvaliant at cs.stanford.edu> 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