Research

I am broadly interested in networks, information theory, online learning, and communications. Some of my recent work has focused on content and service caching in networks, online learning with oracle queries, and inference on graphs. I discuss these topics briefly below, along with some past projects as well.

The material here might be a little outdated, please see the Publications page for recent projects [last updated April 2021].

Online learning with advice

We consider scenarios where we have a random source generating symbols from some unknown distribution or a large high-dimensional database. However, we can access the symbols / entries only by querying an oracle which might provide some incomplete/noisy information. We study problems of property estimation such as identifying the mode or heavy hitters of the underlying distribution, as well as solving computationally challenging problems over large databases such as clustering and k-centers. For such problems, we identify the fundamental query complexity under various oracle models and also design sequential algorithms which adaptively decide what queries to send to the oracle at each stage and can complete the task using near-optimal number of queries.

Selected recent publications:

Greedy k-centers from Noisy Distance Samples, with N. Jali and S. Moharir
Query complexity of heavy hitter estimation, with S. Sarmasarkar and K. S. Reddy.
Query Complexity of k-NN based Mode Estimation, with A. Singhal, S. Pirojiwala, ITW 2021
Sequential Mode Estimation with Oracle Queries, with D. Shah, T. Choudhury and A. Gopalan, AAAI 2020

Service hosting at the edge

Widespread adoption of smartphones and other handheld devices over the last decade has been accompanied with the development of a wide variety of mobile applications providing a plethora of services. These applications often rely on cloud computing platforms to enable the delivery of high-quality performance anytime, anywhere to resource constrained mobile devices. However, the last few years have seen the emergence of applications based on machine learning, computer vision, augmented/virtual reality (AR/VR) etc. which are pushing the limits of what cloud computing platforms can reliably support in terms of the required latency and bandwidth. This is largely due to the significant distance between the end user and the cloud server, which has led the academia and the industry to propose a new paradigm called edge computing whose basic tenet is to bring storage and computing infrastructure closer to the end users. This can help enable applications with ultra-small network latency and/or very high bandwidth requirements, which cannot be reliably supported by the backhaul connection.

While there are now several industry offerings of dedicated edge computing platforms, e.g., Amazon Web Services and Microsoft Azure, there have also been proposals to augment cellular base stations and WiFi access points so that they can act as edge servers. This rapid proliferation of shared edge computing platforms has enabled application service providers to deploy a wide variety of services with stringent latency and high bandwidth requirements. A key advantage of these platforms is that they provide pay-as-you-go flexibility by charging clients in proportion to their resource usage through short-term contracts. This affords the client significant cost-saving opportunities, by dynamically deciding when to host its service on the platform, depending on the changing intensity of requests. Our work focuses on designing online algorithms which enable application providers to decide when and what part of their service to host at the edge, so as to minimize cost while maintaining the required quality of service.

Selected recent publications:

Online Partial Service Hosting at the Edge, with L. Narayana, M. Agarwala, and S. Moharir
RetroRenting: An Online Policy for Service Caching at the Edge, with L. Narayana and S. Moharir, WiOpt 2020.
Partial Service Caching at the Edge, with R. S. Prakash, V. Kavitha, and S. Moharir, CCDWN workshop at WiOpt 2020.

Content Caching and Delivery over Networks

Traditionally, communication networks have been connection-centric, i.e., their operation is based on establishing session between given end hosts. However, as multimedia content streaming and downloads start to dominate internet traffic, their is a growing push towards a more content-centric architecture. Nodes in the network will be equipped with storage and users can dynamically search for locations which have cached their requested files and thus obtain them, rather than looking to connect to a specific end-host.

Recent work has started exploring the role of storage caches in wireless networks and has shown that joint design of cache content and multicast delivery schemes can lead to significant gains over traditional caching schemes, where caches replicate popular content and deliver content via orthogonal unicast transmissions. While prior work focused on single-hop networks and uniformly popular content, we build on this work by extending it to more general network topologies and access structures, as well as adressing non-uniform popularity profiles and privacy concerns.

Selected recent publications:

Rate-Memory Trade-off for Multi-access Coded Caching with Uncoded Placement, with K. S. Reddy, IEEE Transactions on Communications, Jun. 2020.
Resource Pooling in Large-scale Content Delivery Systems, with K. S. Reddy and S. Moharir, IEEE Transactions on Communications, Mar. 2020.
Caching with Partial Adaptive Matching, with J. Hachem, S. Moharir, and S. Diggavi, IEEE Journal on Selected Areas in Communications, Special issue on Caching for Communication Systems and Networks, Aug. 2018.
Private Coded Caching, with Vaishakh. R., P. Panda, and V. Prabhakaran, IEEE Transactions on Information Forensics and Security, Mar. 2018.

Network Inference under Incomplete/Noisy Measurements

There are many target applications, for example in social and biological networks, where model parameters regarding the underlying network or spreading process might be apriori unknown and one might have to infer key properties such as network connectivity and inter-agent influence using empirical observations. Furthermore, in many of these applications, the large scale of the network implies that the available data is incomplete and/or noisy. The goal is to design computationally efficient inference algorithms with resilience to sparsity and noise in the empirical data.

For example, consider a rumor or a trend spreading through a social network with the empirical data indicating which nodes are infected by it. Due to the large scale of the network, it is infeasible to collect data about the infection states of all nodes in the network. Furthermore, the collected data might not always represent the ground truth. An infected user in a Twitter network might not re-tweet the rumor, and thus lead us to believe that it is uninfected, while still helping spread the rumor through other means of communication such as email, text messages, etc. Given such incomplete/noisy data, we study inference algorithms for identifying the source of the rumor in the network.

Selected recent publications:

Jordan centre in random trees: persistence and distance to root with S. Pattathil and D. Shah, Journal of Complex Networks (Oxford University Press), Sep. 2019.
Stochastic Approximation Algorithms for Rumor Source Inference on Graphs, with A. Kalvit and V. S. Borkar, Performance Evaluation, Aug. 2019.
Temporally Agnostic Rumor Source Detection, with A. Kumar and V. Borkar, IEEE Transactions on Signal and Information Processing over Networks, Special issue on Distributed Information Processing in Social Networks, Jun. 2017.

Past Projects

Security and Privacy in Cyber-Physical Systems

Critical infrastructures such as the electrical grid and transportation and water distribution networks are increasingly being controlled and monitored using networks, consisting of tiny devices capable of sensing, communication, and computation. Such cyber-physical systems represent a networked integration of several distributed components representing physical entities as well as computation units, resulting in a tight coupling between the states and actions of the various components. The inherently distributed nature of such systems makes them vulnerable to security breaches and malicious attacks. Furthermore, coordinated attacks on inter-dependent constituents might lead to complex outcomes which cannot be dealt with by simply securing the individual units.

Over the past year, I have been involved in the ``Secure Cyber-Physical Systems" initiative at UCLA, an inter-disciplinary project involving researchers from information theory, control systems, and cryptography. Through this project, I have started collaborating on problems involving the design of resilient state-estimation schemes in distributed control systems, with provable privacy and security guarantees against attacks on the output sensors and state observers.

Related Publications:

Secure State Estimation and Control Using Multiple (insecure) Observers, S. Mishra, N. Karamchandani, P. Tabuada, and S. Diggavi, CDC 2014.

Function Computation over Networks

Consider a set of users, connected via communication network. Each user has a message and we are interested in computing a certain target function of the user messages. This general problem of network computation arises in a wide variety of engineering applications. Examples include environmental monitoring, intrusion detection, distributed consensus, file synchronization, and crowdsourcing. The goal of a system designer is to design efficient schemes for computing different target functions over various network topologies and under different inter-node communication models. Over a sequence of works, some of which were part of my Ph.D. thesis, I have explored several different aspects of this problem, such as characterizing the optimal performance in terms of different metrics such as computation rate, number of transmissions, and delay; design of distributed schemes suitable for dynamic networks with changing topology or target functions; and a comparison of joint communication-computation schemes vs separation-based schemes.

Related Publications:

Network Coding for Computing: Cut-set Bounds, IEEE Trans. on Information Theory, Feb. 2011.
Time and Energy Complexity of Function Computation over Networks, IEEE Trans. on Information Theory, Dec. 2011.
Function Computation via Subspace Coding, Elsevier Physical Communications, Mar. 2013.
Computation over Mismatched Channels, IEEE Journal on Selected Areas in Communications, Apr. 2013.
Linear Codes, Target Function Classes, and Network Computing Capacity, IEEE Trans. on Information Theory, Sep. 2013.

Cooperation in multi-access networks

We explore the effect of allowing cooperation between the users in a multi-access network, to improve system performance by avoiding collisions and idle time or frequency slots. We place the problem in a coalitional game theory framework and study the effect of cooperation with respect to two different schemes: one, an unregulated access model where each user can transmit at any time, but multiple simultaneous transmissions result in interference; and second, a time-division regulated access model where users get exclusive channel access in a round-robin fashion. We study the stable coalition structures that emerge in each of these cases, and also explore the effect of a cost of establishing cooperation among users.

Related Publication:

Agile Broadcast Services: Addressing the Wireless Spectrum Crunch via Coalitional Game Theory, accepted for publication in the IEEE Trans. on Wireless Communications, Oct. 2013.

Google Sites

Report abuse