Skip to main content.
Advanced search >
<< Back to previous page Print

<< Wednesday, May 01, 2013 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

[Dissertation Talk] Cooperative Data Exchange Problem: Algorithms and Complexity

Seminar: Departmental | May 1 | 2-3 p.m. | 400 Cory Hall

Nebojsa Milosavljevic, UC Berkeley, EECS Department

Electrical Engineering and Computer Sciences (EECS)

In this talk I am going to present the data exchange problem where a set of clients is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that each client can transmit messages over a noise-free and interference-free channel to the remaining clients, the goal is for each client to gain access to the file while minimizing some communication cost. We provide a polynomial-time deterministic algorithm that finds an optimal communication scheme w.r.t. the transmission cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic scheme.