Karthik Abinav Sankararaman*

I am currently a research scientist at Facebook. Previously, I finished my PhD at the Department of Computer Science at University of Maryland, College Park (I also received an M.S. degree from the same department). I was fortunate to work closely with these awesome researchers. Even before that, I obtained a B.Tech (Hons), with a major in Computer Science and a minor in Operations Research, from Indian Institute of Technology, Madras. My brother and I spent our childhood days in the beautiful city of Bangalore, India.
My research interests broadly span the intersection of Algorithms, Machine Learning and Operations Research. I am interested in both foundations and applications of problems that broadly fall in these domains. I am especially interested in research that spans the full spectrum of theory to practice (i.e., theory informing practice and applications informing theory).
My current focus is to design foundational algorithms and tools for robust decision making under uncertainty and apply it in the real-world (recent applications include ride-share and human computation). This encompasses topics in probability, optimization, matching-based market design, online machine learning, causal inference and theoretical computer science.
I am always open to working on projects tied to other application areas (especially those with a human component) which require principled algorithmic approaches. Feel free to contact me!

Algorithmic decision making is ubiquitous in modern society; it dictates how we travel, what we spend our money, attention and time on, where we eat among others. With algorithms playing such a key role, we want them to work for everybody in every scenario; formally this translates to algorithm receiving inputs from multiple models of the environment and optimizing different objective functions. Often we want the same (or with minimal modifications) algorithm to be "robust" in the sense that they work with multiple constraints seemlessly; sometimes the algorithm need not even know which of these environments it is working in! Some aspects of robustness my research focusses on are as follows.

  • Realtime v/s Offline Data: Compared to traditional algorithm design, modern applications require algorithms that operate on real-time data. The input is given as a sequence (possibly adapting to the previous decisions made by the algorithm) and the performance of the algorithm is compared against an algorithm that received the entire data at once before making any decisions; we want the performance to comparably good (often measured using regret or competitive ratio). Often there are additional constraints (e.g., fairness-efficiency tradeoff below, limited supply of goods, avoiding recency bias) which further make the task difficult. This class of problems are what is commonly called as online machine learning.

  • Fairness-Efficiency Tradeoff: The goal is to design the same algorithm that provides the optimal tradeoff between any given fairness metric (e.g., group level fairness) while also maintaining worst-case global efficiency guarantees. One example of fairness is to ensure that the algorithm does not amplify existing societal biases in the quest to maximize utility. However, fairness issues can also broadly manifest in other scenarios where we want to provide "equal service for equal requests".

  • Easy v/s Hard inputs: The goal is to design a single algorithm that performs very well when the given environment/instance is "easy" while still achieving optimal guarantees in the "hard" scenarios. The most common notion of "easy" and "hard" environments is that the input is obtained as a sample from a distribution (i.e., i.i.d. assumption in statistical machine learning) in the easy case and that an adaptive adversary who is strategic to the choice the algorithm makes provides the input (i.e., adversarial ML) in the hard case. Easy v/s Hard distinction also refers to fine-grained analysis of algorithms for a given modelling of the input (e.g., stochastic or adversarial).

  • Scarce v/s Infinite Data: The goal is to answer when can machine learning algorithms that are designed with the assumption that we have sufficient data also provably work well when we have limited data? For example, provable causal inference algorithms assume that we have infinite correlation data at our disposal. While this assumption might apriori be reasonable in some applications, in some other applications this is far from reality. Collecting large enough correlation samples can be expensive, time-consuming and sometimes impossible. Thus, it is important to understand when algorithms designed for the infinite data regime also work in the face of limited data and/or design new algorithms that work well with limited data.

  • I like reading (through non-fiction books), discussing (with friends) and understanding topics involving Politics, Spirituality, Cognitive Psychology, Philosophy and Communicable Diseases (particularly HIV). Recently, I was introduced to the sport of Bouldering and dabble with it from time-to-time.

    *I usually go by either Karthik or Abinav. If you want to use my last name, please see the syllables for help.
    (Syllables: Kar/thik A/bi/nav San/kar/a/ra/man)

    My name in languages I speak, in decreasing order of proficiency!
    Language Karthik Abinav Sankararaman
    Tamil கார்த்திக் அபினவ் சங்கரராமன்
    Kannada ಕಾರ್ತಿಕ್ ಅಬಿನವ್ ಸಂಕರರಾಮನ್
    Hindi कार्तिक अबिन सन्कररामन

    Conference Publications

    (In (almost) all papers, the authors chose the convention of alphabetical order by last names)

    (C13) "Mix and Match: Markov Chains and Mixing Times in Matching for Rideshare"
    Joint Work with Mike Curry, John Dickerson, Aravind Srinivasan, Yuhao Wan, Pan Xu
    The 15th Conference on Web and Internet Economics (WINE), 2019

    Abstract: Rideshare platforms such as Uber and Lyft dynamically dispatch drivers to match riders' requests. We model the dispatching process in rideshare as a Markov chain that takes into account the geographic mobility of both drivers and riders over time. Prior work explores dispatch policies in the limit of such Markov chains; we characterize when this limit assumption is valid, under a variety of natural dispatch policies. We give explicit bounds on convergence in general, and exact (including constants) convergence rates for special cases. Then, on simulated and real transit data, we show that our bounds characterize convergence rates---even when the necessary theoretical assumptions are relaxed. Additionally these policies compare well against a standard reinforcement learning algorithm which optimizes for profit without any convergence properties.

    Keywords: Machine Learning; Randomized Algorithms; Rideshare; Markov Chains

    (C12) "Adversarial Bandits with Knapsacks"
    Joint Work with Nicole Immorlica, Robert Schapire, Aleksandrs Slivkins
    The 60th IEEE Symposium on Foundations of Computer Science (FOCS), 2019
    INFORMS Workshop on Market Design, 2019

    Paper Poster

    Abstract: We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the “classic” adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to algorithm’s reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version, and use it as a subroutine to solve the latter.

    Keywords: Online Learning; Machine Learning; Randomized Algorithms; Theory of Computation

                      title={Adversarial Bandits with Knapsacks},
                      author={Immorlica, Nicole and Sankararaman, Karthik Abinav and Schapire, Robert and Slivkins, Aleksandrs},
                      booktitle={IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)},
    (C11) "Stability of Linear Structural Equation Model of Causal Inference"
    Joint Work with Navin Goyal and Anand Louis
    The 35th Conference on Uncertainty in Artificial Intelligence (UAI), 2019
    NeurIPS Workshop on Causality, 2018

    Paper Poster

    Abstract: We consider the numerical stability of the parameter recovery problem in Linear Structural Equation Model (LSEM) of causal inference. A long line of work starting from Wright (1920) has focused on understanding which sub-classes of LSEM allow for efficient parameter recovery. Despite decades of study, this question is not yet fully resolved. The goal of this paper is complementary to this line of work; we want to understand the stability of the recovery problem in the cases when efficient recovery is possible. Numerical stability of Pearl’s notion of causality was first studied in Schulman and Srivastava (2016) using the concept of condition number where they provide ill-conditioned examples. In this work, we provide a condition number analysis for the LSEM. First we prove that under a sufficient condition, for a certain sub-class of LSEM that are bow-free (Brito and Pearl (2002)), the parameter recovery is stable. We further prove that randomly chosen input parameters for this family satisfy the condition with a substantial probability. Hence for this family, on a large subset of parameter space, recovery is numerically stable. Next we construct an example of LSEM on four vertices with unbounded condition number. We then corroborate our theoretical findings via simulations as well as real-world experiments for a sociology application. Finally, we provide a general heuristic for estimating the condition number of any LSEM instance.

    Keywords: Causal Inference; Machine Learning; Robust Algorithms

                      author = {Sankararaman, Karthik Abinav and Louis, Anand and Goyal, Navin},
                      title = {Stability Of Linear Structural Equation Models Of Causal Inference},
                      booktitle = {Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence},
                      series = {UAI '19},
                      year = {2019},
    (C10) "Online Resource Allocation with Matching Constraints"
    Joint Work with John Dickerson, Kanthi Sarpatwar, Aravind Srinivasan, Kun-Lung Wu, Pan Xu
    The 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019

    Paper Code+Dataset

    Abstract: Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi-Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type $j$ arrives. Assigning this job to a server $i$ yields a profit w_{i, j} while consuming a_e \in [0, 1]^K quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications

                          author = {Dickerson, John P. and Sankararaman, Karthik Abinav and Sarpatwar, Kanthi Kiran and Srinivasan, Aravind and Wu, Kun-Lung and Xu, Pan},
                          title = {Online Resource Allocation with Matching Constraints},
                          booktitle = {Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems},
                          series = {AAMAS '19},
                          year = {2019},
                          isbn = {978-1-4503-6309-9},
                          pages = {1681--1689},
                          numpages = {9}
    (C9) "A Unified Approach to Online Matching with Conflict-Aware Constraints"
    Joint Work with Pan Xu, Yexuan Shi, Hao Cheng, John Dickerson, Aravind Srinivasan, Yongxin Tong, Leonidas Tsepenekas
    The 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019


    Abstract: Online bipartite matching and allocation models are widely used to analyze and design markets such as Internet advertising, online labor, and crowdsourcing. Traditionally, vertices on one side of the market are fixed and known a priori, while vertices on the other side arrive online and are matched by a central agent to the offline side. The issue of possible conflicts among offline agents emerges in various real scenarios when we need to match each online agent with a set of offline agents. For example, in event-based social networks (e.g., Meetup), offline events conflict for some users since they will be unable to attend mutually-distant events at proximate times; in advertising markets, two competing firms may prefer not to be shown to one user simultaneously; and in online recommendation systems (e.g., Amazon Books), books of the same type conflict with each other in some sense due to the diversity requirement for each online buyer. The conflict nature inherent among certain offline agents raises significant challenges in both modeling and online algorithm design. In this paper, we propose a unifying model, generalizing the conflict models proposed in (She et al., TKDE 2016) and (Chen et al., TKDE 16). Our model can capture not only a broad class of conflict constraints on the offline side (which is even allowed to be sensitive to each online agent), but also allows a general arrival pattern for the online side (which is allowed to change over the online phase). We propose an efficient linear programming (LP) based online algorithm and prove theoretically that it has nearly-optimal online performance. Additionally, we propose two LP-based heuristics and test them against two natural baselines on both real and synthetic datasets. Our LP-based heuristics experimentally dominate the baseline algorithms, aligning with our theoretical predictions and supporting our unified approach.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications

                          author = {Xu, Pan and Shi, Yexuan and Cheng, Hao and Dickerson, John P. and Sankararaman, Karthik Abinav and Srinivasan, Aravind
                          and Tong, Yongxin and Tsepenekas, Leonidas},
                          title = {A Unified Approach to Online Matching and Conflict-Aware Constraints},
                          booktitle = {Proceedings of the 33rd AAAI Conference on Artificial Intelligence},
                          series = {AAAI '19},
                          year = {2019}
    (C8) "Balancing Relevance and Diversity in Online Matching via Submodularity"
    Joint Work with John Dickerson, Aravind Srinivasan, Pan Xu
    The 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019

    Paper Code+Dataset

    Abstract: In bipartite matching problems, vertices on one side of a bipartite graph are paired with those on the other. In its online variant, one side of the graph is available offline, while vertices on the other arrive online and are irrevocably and immediately matched (or ignored) by an algorithm. Examples of such problems include matching workers to firms, advertisers to keywords, organs to patients, and so on. Much of the literature focuses on maximizing the total relevance modeled via total weight of the matching. However, in many real-world problems, it is also important to consider contributions of diversity: hiring a diverse pool of candidates, displaying a relevant but diverse set of ads, and so on. In this paper, we propose the Online Submodular Bipartite Matching (OSBM) problem, where the goal is to maximize a submodular function f over the set of matched edges. This objective is general enough to capture the notion of both diversity (e.g., a weighted coverage function) and relevance (e.g., the traditional linear function) as well as many other natural objective functions occurring in practice (e.g., limited total budget in advertising settings). We propose novel algorithms that have provable guarantees and are essentially optimal when restricted to various special cases. We also run experiments on real-world and synthetic datasets to validate our algorithms.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications

                        title={Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity},
                        author={Dickerson, John P and Sankararaman, Karthik A and Srinivasan, Aravind and Xu, Pan},
                        booktitle = {Proceedings of the 33rd AAAI Conference on Artificial Intelligence},
                        series = {AAAI '19},
                        year = {2019}
    (C7) "Assigning Tasks to Workers based on Historical Data: Online Matching with Two-sided Arrivals"
    Joint Work with John Dickerson, Aravind Srinivasan, Pan Xu
    The 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018

    Paper Code+Dataset

    Abstract: Efficient allocation of tasks to workers is a central problem in crowdsourcing. In a typical setting, different workers arrive at different times. Similarly, different tasks arrive at different times. The goal is to assign the available workers to tasks, such that we are able to complete as many tasks as possible. Usually, the tasks are heterogeneous and have different rewards. Hence, we would like to maximize the total reward (as opposed to just the number of completed tasks). Often, the arrival times of worker "types" and task "types" are not erratic and can be predicted from historical data. In this paper, we model the problem to account for this history and propose a new mathematical model, called Online Matching with Two-Sided Arrival (OM-TSA). We have a known bipartite graph G = (U,V,E) where U is the set of worker types and V is the set of task types. An edge e = (u, v) exists iff worker u is compatible with task v. The setting proceeds in rounds for T time-steps. At each time-step, a worker u from U and a task v from V are sampled independently from two respective (known) distributions. Further, we assume the sampling processes are independent and identical across the T rounds. We assume that (1) when a worker u arrives, they stay in the sys- tem until matched and (2) when a task v arrives, it needs to be assigned to an available worker u immediately (and obtaining a reward w(u, v)); if not, we do not get any reward for this task (and the action is irrevocable). Our goal is to maximize the expected reward. Our model is a significant generalization of the classical online matching model, where one of the sets U and V , say U, is assumed to be available offline. We relax this assumption to capture the transient nature of worker arrivals. For the general version of OM-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OM-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.345. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all non-adaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0.581 (unconditionally), even for the special case of OM-TSA with homogenous tasks (i.e., all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process) called the two-stage birth-death process, which may be of independent interest. Finally, we perform numerical experiments on both simulated as well as two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications

                      author = {Dickerson, John P. and Sankararaman, Karthik Abinav and Srinivasan, Aravind and Xu, Pan},
                      title = {Assigning Tasks to Workers based on Historical Data: Online Matching with Two-sided Arrivals},
                      booktitle = {Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems},
                      series = {AAMAS '18},
                      year = {2018},
    (C6) "Combinatorial Semi-Bandits with Knapsacks"
    Joint Work with Aleksandrs Slivkins
    The 21st International Conference on Artificial Intelligence and Statistics (AIStats), 2018
    (Invited for Oral Presentation)
    (Top 5% of submissions)

    Paper Simulations Poster

    Abstract: This paper unifies two lines of work on multi-armed bandits, Bandits with Knapsacks (BwK) and semi-bandits. The former concerns scenarios with limited "resources" consumed by the algorithm, e.g., limited inventory in a dynamic pricing problem. The latter has a huge number of actions, but there is combinatorial structure and additional feedback which makes the problem tractable. Both lines of work has received considerable recent attention, and are supported by numerous application examples. We define a common generalization, and design a general algorithm for this model. Our regret rates are comparable with those for BwK and semi-bandits in general, and essentially optimal for important special cases.

    Keywords: Randomized Algorithms; Online Learning; Theory of Computation; Machine Learning

                        title={Combinatorial semi-bandits with knapsacks},
                        author={Sankararaman, Karthik Abinav and Slivkins, Aleksandrs},
                        booktitle={International Conference on Artificial Intelligence and Statistics},
                        series = {AIStats '18},
    (C5) "Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources"
    Joint Work with John Dickerson, Aravind Srinivasan, Pan Xu
    The 32nd AAAI Conference on Artificial Intelligence (AAAI), 2018
    (Oral Presentation)

    Paper Code

    Abstract: Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1/2 − ε for any given ε > 0. We also show that no non-adaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching service. We also present heuristics that perform well in practice.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications

                          title={Allocation problems in ride-sharing platforms: Online matching with offline reusable resources},
                          author={Dickerson, John P and Sankararaman, Karthik A and Srinivasan, Aravind and Xu, Pan},
                          booktitle={Proceedings of the 32nd AAAI Conference on Artificial Intelligence},
    (C4) "Algorithms to Approximate Column-Sparse Packing Programs"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    The 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018


    Abstract: Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integrality-gap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).

    Keywords: Randomized Algorithms; Theory of Computation

                       title={Algorithms to approximate column-sparse packing problems},
                       author={Brubach, Brian and Sankararaman, Karthik A and Srinivasan, Aravind and Xu, Pan},
                       booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
                       organization={Society for Industrial and Applied Mathematics}
    (C3) "Attenuate Locally, Win Globally: Attenuation-based Frameworks for Online Stochastic Matching with Timeouts"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    The 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017


    Abstract: The Online Stochastic Matching with Timeouts problem introduced by Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra (Algorithmica, 2012) models matching markets (e.g. E-Bay, Amazon). Buyers arrive from an independent and identically distributed (i.i.d.) known distribution on buyer profiles and can be shown a list of items one at a time. Each buyer has some probability of purchasing each item and a limit (timeout) on the number of items they can be shown. Bansal et al. (Algorithmica, 2012) gave a 0.12-competitive algorithm which was improved by Adamczyk, Grandoni, and Mukherjee (ESA, 2015) to 0.24. We present an online attenuation framework that uses an algorithm for offline stochastic matching as a black box. Our main contributions are as follows. On the upper bound side, we show that this framework combined with a black box adapted from Bansal et al. (Algorithmica, 2012) yields an online algorithm which nearly doubles the ratio to 0.46. On the lower bound side, we show that no algorithm can achieve a ratio better than 0.632 using the common LP for this problem. We then introduce a natural generalization: Online Stochastic Matching with Two-sided Timeouts in which both online and offline vertices have timeouts. Our framework provides the first algorithm for this problem achieving a ratio of 0.31. We accomplish this by proposing a new black box algorithm for offline stochastic matching on star graphs, which may be of independent interest. This new black box improves the approximation ratio for the offline stochastic matching problem on star graphs from 0.5 by Adamczyk et al. (ESA 2015) to 0.56.

    Keywords: Randomized Algorithms; Online Algorithms; Theory of Computation

                        title={Attenuate locally, win globally: An attenuation-based framework for online stochastic matching with timeouts},
                        author={Brubach, Brian and Sankararaman, Karthik Abinav and Srinivasan, Aravind and Xu, Pan},
                        booktitle={Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems},
                        organization={International Foundation for Autonomous Agents and Multiagent Systems}
    (C2) "New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    The 24th Annual European Symposium on Algorithms (ESA), 2016


    Abstract: We develop algorithms with improved competitive ratios for some basic variants of the known i.i.d. arrival model with integral arrival rates, including (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam to 0.705 and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu to 0.7299. We also consider two extensions, one is known I.I.D. with non-integral arrival rate and stochastic rewards. The other is known I.I.D. b-matching with non-integral arrival rate and stochastic rewards. We present a simple non-adaptive algorithm which works well simultaneously on the two extensions.

    Keywords: Randomized Algorithms; Online Algorithms; Theory of Computation

                        title={New algorithms, better bounds, and a novel model for online stochastic matching},
                        author={Brubach, Brian and Sankararaman, Karthik Abinav and Srinivasan, Aravind and Xu, Pan},
                        booktitle={24th Annual European Symposium on Algorithms (ESA 2016)},
                        organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
    (C1) "Ensuring Privacy in Location Based Services: An Approach Based on Opacity Enforcement"
    Joint work with Yi-Chin Wu, St`ephane Lafortune.
    The 14th International Workshop of Discrete Event Systems (WODES), 2014


    Abstract: With the proliferation of mobile devices, Location-Based Services (LBS) that provide networked services based on users’ locations have become increasingly popular. Such services, providing personalized and timely information, have raised privacy concerns such as unwanted revelation of users’ current locations to potential stalkers. In this work, we show that this problem can be formally (for first time) addressed using the notion of opacity in discrete event systems. We use non-deterministic finite-state automata to capture the mobility patterns of users and label the transitions by the location information in the queries. Using opacity verification techniques, we show that the technique of sending cloaking queries to the server can still reveal the exact location of the user. To enforce location privacy, we apply the opacity enforcement technique by event insertion. Specifically, we synthesize suitable insertion functions that insert fake queries into the cloaking query sequences. The generated fake queries are always consistent with the mobility model of the user and provably ensure privacy of the user’s current location. Finally, to minimize the overhead from fake queries, we design an optimal insertion function that introduces minimum average number of fake queries.

    Keywords: Discrete Event Systems; Formal Verification; Applications

                        title={Ensuring privacy in location-based services: An approach based on opacity enforcement},
                        author={Wu, Yi-Chin and Sankararaman, Karthik Abinav and Lafortune, St{\'e}phane},
                        journal={IFAC Proceedings Volumes},

    Journal Publications

    (J1) "Attenuate Locally, Win Globally: Attenuation-based Frameworks for Online Stochastic Matching with Timeouts"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    Algorithmica, 2019

    (J2) "Algorithms to approximate column-sparse packing problems"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    ACM Transactions on Algorithms (TALG), 2019

    Working Papers, Theses and Surveys

    (W1) "The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent"
    Joint Work with Soham De, Zheng Xu, Ronny Huang, Tom Goldstein
    NeurIPS Workshop on Integration of Deep Learning Theories, 2018

    Paper Poster

    Abstract: The goal of this paper is to study why stochastic gradient descent (SGD) is efficient for neural networks, and how neural net design affects SGD. In particular, we investigate how overparameterization -- an increase in the number of parameters beyond the number of training data -- affects the dynamics of SGD. We introduce a simple concept called gradient confusion. When confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, we show that SGD has better convergence properties than predicted by classical theory. Using theoretical and empirical results, we study how overparameterization affects gradient confusion, and thus the convergence of SGD, on linear models and neural networks. We show that increasing the number of parameters of linear models or increasing the width of neural networks leads to lower gradient confusion, and thus faster and easier model training. We further show how overparameterization by increasing the depth of neural networks results in higher gradient confusion, making deeper models harder to train. Finally, we observe empirically that batch normalization and skip connections reduce gradient confusion, which helps reduce the training burden of deep networks.

    Keywords: Deep Learning; Machine Learning; Optimization; Theory of Computation

    (Thesis 2) "Sequential Decision Making with Limited Resources"
    (Not proof-read for typos)
    PhD Thesis 2019, University of Maryland, College Park


    Abstract: One of the goals of Artificial Intelligence (AI) is to enable multiple agents to interact, co-ordinate and compete with each other to realize various goals. Typically, this is achieved via a system which acts as a mediator to control the agents' behavior via incentives. Such systems are ubiquitous and include online systems for shopping (e.g., Amazon), ride-sharing (e.g., Uber, Lyft) and Internet labor markets (e.g., Mechanical Turk). The main algorithmic challenge in such systems is to ensure that they can operate under a variety of informational constraints such as uncertainty in the input, committing to actions based on partial information or being unaffected by noisy input. The mathematical framework used to study such systems are broadly called sequential decision makin} problems where the algorithm does not receive the entire input at once; it obtains parts of the input by interacting (also called "actions") with the environment. In this thesis, we answer the question, under what informational constraints can we design efficient algorithms for sequential decision making problems. The first part of the thesis deals with the Online Matching problem. Here, the algorithm deals with two prominent constraints: uncertainty in the input and choice of actions being restricted by a combinatorial constraint. We design several new algorithms for many variants of this problem and provide provable guarantees. We also show their efficacy on the ride-share application using a real-world dataset. In the second part of the thesis, we consider the Multi-armed bandit problem with additional informational constraints. In this setting, the algorithm does not receive the entire input and needs to make decisions based on partial observations. Additionally, the set of possible actions is controlled by global resource constraints that bind across time. We design new algorithms for multiple variants of this problem that are worst-case optimal. We provide a general reduction framework to the classic multi-armed bandits problem without any constraints. We complement some of the results with preliminary numerical experiments.

    Keywords: Online Matching; Multi-armed Bandits; Machine Learning; Randomized Algorithms; Theory of Computing

    (Thesis 1) "Maximum-Flow problem in undirected graphs"
    Karthik Abinav S
    B.Tech Thesis, 2014, Indian Institute Technology Madras
    (Thesis available on request)

    (Survey 1) "Semi-Bandit Feedback: A survey of results (2015)"

    Teaching Experience

    Recently, I have been working on a series on "Introduction to Online Learning". This covers the theoretical foundations of basic algorithms in both adversarial and stochastic online learning. This is meant to be an introduction to this subject typically covered in an undergraduate machine learning class.

    I have served as an instructor for the following class, teaching along with Bill Gasarch
  • Honors class on Discrete Structures (Spring 2019)

  • I have served as a Teaching Assistant for the following classes during my time at UMD
  • Graduate Algorithms (Spring 2018)
    Instructors: Aravind Srinivasan

  • Design and Analysis of Computer Algorithms (Fall 2016, Spring 2017, Fall 2017, Fall 2018)
    Instructors: Samir Khuller, Jessica Chang, Aravind Srinivasan

  • Discrete Structures (Fall 2014 and Spring 2015)
    Instructors: Clyde Kruskal, Fawzi Emad

  • Introduction to Programming (Fall 2015 and Spring 2016)
    Instructors: Nelson Padua-Perez, Fawzi Emad

  • As an undergrad I have served as a Teaching Assistant at IITM.
  • Paradigms of Programming(IITM)
    Instructors: Narayanaswamy NS
  • Industry/Other Research Experience

    Microsoft Research, New York City

    I spent the Summer 2018 (June-September) at Microsoft Research, New York City working with Nicole Immorlica, Rob Schapire and Alex Slivkins. We studied problems in Online Learning.

    Indian Institute of Science and Microsoft Research, Bangalore

    I spent the Summer of 2017 at IISc and Microsoft Research, Bangalore working with Anand Louis and Navin Goyal. We studied problems in Causal Inference.

    IBM Almaden Research Center, San Jose

    I spent the Summer of 2016 at IBM Almaden Research center, working with Prithviraj Sen. We worked on problems in applied machine learning.

    Adobe Inc.

    I spent the Summer of 2015 at Adobe Systems Inc, at their San Jose office. I worked with the Algorithms team inside the Digital Marketing team headed by Anil Kamath. I was involved in an applied algorithms project in databases. In particular we were working on the Online Entity Resolution problem.

    Miscellanous Writings - Academic and Non-Academic

  • A critique I wrote for the Computational Journalism class.
    The article is a critque on FiveThirtyEight publication Best and Worst Airlines.

  • Final project for the Computational Journalism class on Bias in Google's Autocomplete Suggestion.
    Along with Daniel Trielli, we studied the bias in auto-complete suggestions of various country specific
    domains of Google when searched about entities of other countries.
    (For example, searching about Pakistan in India-specific Google page).
    You can find the code used for the experiments here.
    Article summarizing the methodologies and findings

  • Final class project for the Convex Optimization class.
    Along with Manasij Venkatesh and Aditya Acharya, we looked at sparse representations for speech
    using Convex Optimization based approximations. In particular, we applied techniques from compressed
    sensing literature to speech.
    Report, Poster, code

  • Final class project for the Lower Bounds in Algorithms class.
    Along with Tommy Pensyl and Bartosz Rybicki (visiting from Poland), we studied
    lower bounds for fault tolerant variations of the facility location problem.

  • Feel free to contact me

    The best way to contact me is through email.