Research Experience

Research projects:

1. Sequential Deliberation in Participatory Budgeting
   Advisor: Prof. Ashish Goel, Department of Management Science and Engineering, Stanford
   Introduction: We consider the problem of seqential deliberation in participatory budgeting where randomly sampled agents bargain in rounds with the outcome of the previous round being the diasgreement point for the current round.
   
   • We propose a randomised Nash bargaining scheme which achieves a distortion ratio of 1.66.
     
   • We also show that schemes with a single randomly sampled agent (Randomised Dictator) and two sampled agents (Randomised Diarchy) cannot achieve a distortion ratio better than 2.
     
   • Paper submitted to AAMAS, 2023*
2. Query Complexity of Heavy-Hitter distribution| Bachelor’s Thesis (Aug ‘19 - Jan ‘20)
   Guide : Prof. Nikhil Karamchandani, Department of Electrical Engineering, IIT Bombay
   Introduction: We studied the problem of identifying the subset of elements in the support of an underlying distribution $\mathcal{P}$ whose probability value is larger than a given threshold $\gamma$, by actively querying an oracle to gain information about a sequence $X_1, X_2, \ldots$ of $i.i.d.$ samples drawn from $\mathcal{P}$ under two different query models $(a)$ each query is an index $i$ and the oracle return the value $X_i$ and $(b)$ each query is a pair $(i,j)$ and the oracle gives a binary answer confirming if $X_i = X_j$ or not.
   
   • We propose upper bounds on the query complexity of our algorithm and also derive “matching” lower bounds on any optimal algorithm under both the query models.
     
   • We also consider noisy versions of the two query models and propose upper bounds on algorithms to estimate the desired subset of elements.
     
   • We derive upper bounds on algorithms for an alternate version of this problem where we wish to identify the subset of support elements which is an “outlier” i.e, whose support probability lies above $k$ standard deviations of the mean and design lower bounds on any optimal algorithm under the first query model.
     
   • Paper presented at ISIT, 2021
3. *Thoerems in redundancies in multi-tasking ** (Jan ‘20 - Ongoing)
   *Guide : Prof. Harish Pillai, Deaprtment of Electrical Engineering, IIT Bombay
   Introduction : We study the problem of redundancies during distributed computation. We consider a problem of $n$ jobs(tasks) and $c$ servers with $k$ distinct jobs in each server with each job being present in $r$ servers. We attempt to create distributions to ensure minimum redundancies in jobs when a set of $x$ servers chosen uniformly at random return their jobs.
   • We prove that the expectation of the number of distinct jobs is same irrespective of the distribution chosen.
     
   • We design a sufficient criterion such that the variance of the number of distinct jobs for any $x$ would be the least amongst all distributions.
     
   • We also show that constructions using Balanced Incomplete Block Designs achieved the above requirement for certain values of $n$ and $k$.
     
4. Straggler mitigation under gradient coding| [Report] (Sep ‘20 - Ongoing)
   Guide: Prof. Lalitha Vadlamani, IIIT Hyderabad, Prof. Nikhil Karamchandani, IIT Bombay
   Introduction : This is a synchronous gradient coding problem where the master does not expect the sum of all the $k$-gradients but the sum of any $l=\alpha.k$ gradients would suffice. Each of the $n$ child servers is provided with a set of gradients to compute and transmit one or more linear combinations of them. We aim to design schemes which could tolerate upto $s$-stragglers with minimum number of gradients per worker.
   • Designed schemes attaining the lower bound on the number of gradient data subsets assigned to every worker but with high communication load per worker.
     
   • Proved that the above scheme is “optimal” in the number of gradients assigned to any worker under certain constraints on $n,l$ and $s$.
     
   • We also simulate such schemes using different delay model on machines and show empirically that such schemes may indeed converge faster than full recovery schemes and the ones which don’t use any coding.
     
   • Paper presented at ISIT, 2021
5. On the early spreading rate of COVID-19 in India| [Report] (Mar ‘20 - Apr ‘20)
   Guide: Prof. D.Manjunath, Department of Electrical Engineering, IIT Bombay
   Introduction: We attempted to model the early spreading of CoVID-19 in India and other countries using subtle variations of graphical SIR(Susceptible Infected Recovered) models.
   • Studied various SIR models to approximately model the spread rate of CoVID-19 in India.
     
   • Three different models were simulated for four different countries to estimate the contact rates using the data available on the number of cases.
     
6. Approximately Optimal Arms Identification of a MAB| [Slides] (Aug ‘19 - Nov ‘19)
   Guide : Prof. Sharayu Moharir, Department of Electrical Engineering, IIT Bombay
   Introduction: This is a MAB (Multi Arm Bandit) setting problem where we wish to identify a set of top $m$ arms with $\epsilon$-error tolerance correctly with probability at least $(1-\delta)$. This algorithm proceeds in rounds with each round divided into 2 events- Sampling Strategy and Stoppping Criterion.
   • Modified the stopping criterion and the confidence intervals in a previous work on PAC optimal subsets.
     
   • Theoretically proved $2/3^{rd}$ factor improvement in the pull complexity with the above modifications.