Optimal resource allocation in networks gives rise to some of the most fundamental problems at the intersection of algorithms, stochastic processes, and learning. In this talk, we will discuss our recent contributions to three canonical resource allocation problems, namely caching, routing, and scheduling. First, we will consider the optimal caching problem for single and networked caches. However, instead of minimizing the competitive ratio - the classical metric of choice for caching problems, we will look at the problem from an online learning perspective that minimizes regret. We will show that this viewpoint leads to an entirely new class of caching policies with provably better performance than the classical ones. We will also discuss some converse results on the regret lower bounds for this problem. Next, we will discuss the problem of throughput-optimal dynamic routing of a broad class of traffic, including unicast, multicast, broadcast, and anycast flows on a network with arbitrary link scheduling constraints. We will present a unified algorithmic framework based on precedence relaxations, leading to an efficient policy that provably outperforms the state-of-the-art Backpressure routing algorithm. Finally, we will discuss a user scheduling problem for reliable and fresh information delivery over unreliable wireless channels. However, contrary to the existing literature, which predominantly considers stochastic channels, we investigate a non-stationary environment modeled using a new adversarial framework. We will describe competitive algorithms in this setting along with some approximately tight lower bounds. We will supplement each part of the talk with a set of open problems.
Bio: Abhishek Sinha is currently working as an Assistant Professor in the Department of Electrical Engineering at the Indian Institute of Technology Madras. He received his Ph.D. degree from the Massachusetts Institute of Technology in 2017, where he was associated with the Laboratory for Information and Decision Systems (LIDS). After his Ph.D., Abhishek worked as a senior engineer at Qualcomm Research, San Diego, in the 5G standardization group. He obtained his M.E. degree in Telecommunication Engg. from the Indian Institute of Science, Bangalore, and his B.E. degree in Electronics and Telecommunication Engg. from Jadavpur University, Kolkata, India. He is a recipient of the Best Paper Award in INFOCOM 2018, the Best Paper Award in MobiHoc 2016, Prof. Jnansaran Chatterjee memorial gold medal, and T.P. Saha Memorial gold-centered silver medal from Jadavpur University and Jagadis Bose National Science Talent Search (JBNSTS) scholarship, Kolkata, India. His areas of interest include networks, information theory, theoretical machine learning, and applied probability.
