Network Computing: Limits and Achievability

Nikhil Karamchandani

UCSD & UCLA
Information Theory and Applications Center & Dept. of Electrical Engineering
San Diego & Los Angeles, CA, USA

Abstract:

Consider a set of users connected to a central agent via a communication network. Each user has a message and the agent is interested in recovering a certain target function of the user messages. What is the minimum amount of information that the users need to send across the network so that the agent can achieve its objective? This general problem of network computation can be used to model a wide variety of engineering applications. Examples include environmental monitoring, intrusion detection, distributed consensus, file synchronization, and crowdsourcing. The goal in such problems is to design efficient schemes for computing different target functions over various network topologies. In this talk, we will consider three different models: one-shot computation, repeated computation, and oblivious computation. For each of these models, we study the minimum amount of resources required for successful computation. We find limits on the performance of any computation protocol and also design efficient schemes which come close to these limits. We will also mention several open problems.

Biography:

Nikhil Karamchandani received the B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay in 2005, the M.S. degree in Electrical and Computer Engineering from the University of California at San Diego in 2007, and the Ph.D. degree in Electrical and Computer Engineering from the University of California at San Diego in 2011. He is currently a postdoctoral scholar jointly with the Information Theory and Applications Center at the University of California at San Diego and the Department of Electrical Engineering at the University of California at Los Angeles.