Kanthi Sarpatwar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Kanthi Sarpatwar has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Guy Kortsarz
Computer Science, Rutgers University, Camden, USA
3 shared publications - MohammadTaghi Hajiaghayi
University of Maryland, College Park, USA
3 shared publications - Baruch Schieber
Department of Computer Science New Jersey Institute of Technology
2 shared publications - Hadas Shachnai
Computer Science Department, Technion, Haifa, Israel
2 shared publications - Manish Purohit
University of Maryland
2 shared publications - Robert MacDavid
Rutgers University - Camden
2 shared publications
Latest Publications
- Open Access
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 5777-5778
AI Explainability 360 Toolkit for Time-Series and Industrial Use Cases
With the growing adoption of AI, trust and explainability have become critical which has attracted a lot of research attention over the past decade and has led to the development of many popular AI explainability libraries such as AIX360, Alibi, OmniXAI, etc. Despite that, applying explainability techniques in practice often poses challenges such as lack of consistency between explainers, semantically incorrect explanations, or scalability. Furthermore, one of the key modalities that has been less explored, both from the algorithmic and practice point of view, is time-series. Several application domains involve time-series including Industry 4.0, asset monitoring, supply chain or finance to name a few. The AIX360 library (https://github.com/Trusted-AI/AIX360) has been incubated by the Linux Foundation AI & Data open-source projects and it has gained significant popularity: its public GitHub repository has over 1.3K stars and has been broadly adopted in the academic and applied settings. Motivated by industrial applications, large scale client projects and deployments in software products in the areas of IoT, asset management or supply chain, the AIX360 library has been recently expanded significantly to address the above challenges. AIX360 now includes new techniques including support for time-series modality introducing time series based explainers such as TS-LIME, TS Saliency explainer, TS-ICE and TS-SHAP. It also introduces improvements in generating model agnostic, consistent, diverse, and scalable explanations, and new algorithms for tabular data. In this hands-on tutorial, we provide an overview of the library with the focus on the latest additions, time series explainers and use cases such as forecasting, time series anomaly detection or classification, and hands-on demonstrations based on industrial use-cases selected to demonstrate practical challenges and how they are addressed. The audience will be able to evaluate different types of explanations with a focus on practical aspects motivated by real deployments.
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 5777-5778
Open AccessAI Explainability 360 Toolkit for Time-Series and Industrial Use Cases
With the growing adoption of AI, trust and explainability have become critical which has attracted a lot of research attention over the past decade and has led to the development of many popular AI explainability libraries such as AIX360, Alibi, OmniXAI, etc. Despite that, applying explainability techniques in practice often poses challenges such as lack of consistency between explainers, semantically incorrect explanations, or scalability. Furthermore, one of the key modalities that has been less explored, both from the algorithmic and practice point of view, is time-series. Several application domains involve time-series including Industry 4.0, asset monitoring, supply chain or finance to name a few. The AIX360 library (https://github.com/Trusted-AI/AIX360) has been incubated by the Linux Foundation AI & Data open-source projects and it has gained significant popularity: its public GitHub repository has over 1.3K stars and has been broadly adopted in the academic and applied settings. Motivated by industrial applications, large scale client projects and deployments in software products in the areas of IoT, asset management or supply chain, the AIX360 library has been recently expanded significantly to address the above challenges. AIX360 now includes new techniques including support for time-series modality introducing time series based explainers such as TS-LIME, TS Saliency explainer, TS-ICE and TS-SHAP. It also introduces improvements in generating model agnostic, consistent, diverse, and scalable explanations, and new algorithms for tabular data. In this hands-on tutorial, we provide an overview of the library with the focus on the latest additions, time series explainers and use cases such as forecasting, time series anomaly detection or classification, and hands-on demonstrations based on industrial use-cases selected to demonstrate practical challenges and how they are addressed. The audience will be able to evaluate different types of explanations with a focus on practical aspects motivated by real deployments.
- 21 June 2023
- Published by Springer Nature in Journal of Scheduling
- Vol. 27 (1) , 103-118
The preemptive resource allocation problem
- 21 June 2023
- Published by Springer Nature in Journal of Scheduling
- Vol. 27 (1) , 103-118
The preemptive resource allocation problem
- Open Access
Differentially Private Distributed Data Summarization under Covariate Shift
We envision AI marketplaces to be platforms where consumers, with very less data for a target task, can obtain a relevant model by accessing many private data sources with vast number of data samples. One of the key challenges is to construct a training dataset that matches a target task without compromising on privacy of the data sources. To this end, we consider the following distributed data summarizataion problem. Given K private source datasets denoted by $[D_i]_{i\in [K]}$ and a small target validation set $D_v$, which may involve a considerable covariate shift with respect to the sources, compute a summary dataset $D_s\subseteq \bigcup_{i\in [K]} D_i$ such that its statistical distance from the validation dataset $D_v$ is minimized. We use the popular Maximum Mean Discrepancy as the measure of statistical distance. The non-private problem has received considerable attention in prior art, for example in prototype selection (Kim et al., NIPS 2016). Our work is the first to obtain strong differential privacy guarantees while ensuring the quality guarantees of the non-private version. We study this problem in a Parsimonious Curator Privacy Model, where a trusted curator coordinates the summarization process while minimizing the amount of private information accessed. Our central result is a novel protocol that (a) ensures the curator accesses at most $O(K^{\frac{1}{3}}|D_s| + |D_v|)$ points (b) has formal privacy guarantees on the leakage of information between the data owners and (c) closely matches the best known non-private greedy algorithm. Our protocol uses two hash functions, one inspired by the Rahimi-Recht random features method and the second leverages state of the art differential privacy mechanisms. We introduce a novel "noiseless" differentially private auctioning protocol for winner notification and demonstrate the efficacy of our protocol using real-world datasets.Open AccessDifferentially Private Distributed Data Summarization under Covariate Shift
We envision AI marketplaces to be platforms where consumers, with very less data for a target task, can obtain a relevant model by accessing many private data sources with vast number of data samples. One of the key challenges is to construct a training dataset that matches a target task without compromising on privacy of the data sources. To this end, we consider the following distributed data summarizataion problem. Given K private source datasets denoted by $[D_i]_{i\in [K]}$ and a small target validation set $D_v$, which may involve a considerable covariate shift with respect to the sources, compute a summary dataset $D_s\subseteq \bigcup_{i\in [K]} D_i$ such that its statistical distance from the validation dataset $D_v$ is minimized. We use the popular Maximum Mean Discrepancy as the measure of statistical distance. The non-private problem has received considerable attention in prior art, for example in prototype selection (Kim et al., NIPS 2016). Our work is the first to obtain strong differential privacy guarantees while ensuring the quality guarantees of the non-private version. We study this problem in a Parsimonious Curator Privacy Model, where a trusted curator coordinates the summarization process while minimizing the amount of private information accessed. Our central result is a novel protocol that (a) ensures the curator accesses at most $O(K^{\frac{1}{3}}|D_s| + |D_v|)$ points (b) has formal privacy guarantees on the leakage of information between the data owners and (c) closely matches the best known non-private greedy algorithm. Our protocol uses two hash functions, one inspired by the Rahimi-Recht random features method and the second leverages state of the art differential privacy mechanisms. We introduce a novel "noiseless" differentially private auctioning protocol for winner notification and demonstrate the efficacy of our protocol using real-world datasets. - 1 March 2019
- Published by IBM in IBM Journal of Research and Development
- Vol. 63 (2/3) , 5:1-5:14
Blockchain analytics and artificial intelligence
- 1 March 2019
- Published by IBM in IBM Journal of Research and Development
- Vol. 63 (2/3) , 5:1-5:14
Blockchain analytics and artificial intelligence
- Open Access
The Preemptive Resource Allocation Problem
We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resources to user requests (jobs) in such settings, we consider the following variants of the classic {\em resource allocation problem} (\textsf{RAP}). The input to our problems is a set $J$ of jobs and a set $M$ of homogeneous hosts, each has an available amount of some resource. A job is associated with a release time, a due date, a weight, and a given length, as well as its resource requirement. A \emph{feasible} schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. A crucial distinction between classic {\textsf{RAP}} and our problems is that we allow preemption and migration of jobs, motivated by virtualization techniques. We consider two natural objectives: {\em throughput maximization} (\textsf{MaxT}), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in $M$, and {\em resource minimization} (\textsf{MinR}), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We first present a $\Omega(1)$-approximation algorithm for \textsf{MaxT} instances where time-windows form a laminar family of intervals. We then extend the algorithm to handle instances with arbitrary time-windows, assuming there is sufficient slack for each job to be completed. For \textsf{MinR} we study a more general setting with $d$ resources and derive an $O(\log d)$-approximation for any fixed $d \geq 1$, under the assumption that time-windows are not too small. This assumption can be removed leading to a slightly worse ratio of $O(\log d\log^* T)$, where $T$ is the maximum due date of any job.Open AccessThe Preemptive Resource Allocation Problem
We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resources to user requests (jobs) in such settings, we consider the following variants of the classic {\em resource allocation problem} (\textsf{RAP}). The input to our problems is a set $J$ of jobs and a set $M$ of homogeneous hosts, each has an available amount of some resource. A job is associated with a release time, a due date, a weight, and a given length, as well as its resource requirement. A \emph{feasible} schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. A crucial distinction between classic {\textsf{RAP}} and our problems is that we allow preemption and migration of jobs, motivated by virtualization techniques. We consider two natural objectives: {\em throughput maximization} (\textsf{MaxT}), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in $M$, and {\em resource minimization} (\textsf{MinR}), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We first present a $\Omega(1)$-approximation algorithm for \textsf{MaxT} instances where time-windows form a laminar family of intervals. We then extend the algorithm to handle instances with arbitrary time-windows, assuming there is sufficient slack for each job to be completed. For \textsf{MinR} we study a more general setting with $d$ resources and derive an $O(\log d)$-approximation for any fixed $d \geq 1$, under the assumption that time-windows are not too small. This assumption can be removed leading to a slightly worse ratio of $O(\log d\log^* T)$, where $T$ is the maximum due date of any job. - 1 January 2018
- Published by Elsevier in Information Processing Letters
- Vol. 129, 31-34
On maximum leaf trees and connections to connected maximum cut problems
- 1 January 2018
- Published by Elsevier in Information Processing Letters
- Vol. 129, 31-34
On maximum leaf trees and connections to connected maximum cut problems
- 12 November 2015
- Published by Springer Nature
- p. 693-704
Approximation Algorithms for Connected Maximum Cut and Related Problems
- 12 November 2015
- Published by Springer Nature
- p. 693-704
Approximation Algorithms for Connected Maximum Cut and Related Problems
- Open Access
Approximation Algorithms for Connected Maximum Cut and Related Problems
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S $\subseteq$ V that maximizes the number of edges in the cut \delta(S) such that the induced graph G[S] is connected. We present the first non-trivial \Omega(1/log n) approximation algorithm for the connected maximum cut problem in general graphs using novel techniques. We then extend our algorithm to an edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in stark contrast to the classical max-cut problem, we show that the connected maximum cut problem remains NP-hard even on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the connected maximum cut problem on planar graphs and more generally on graphs with bounded genus.Open AccessApproximation Algorithms for Connected Maximum Cut and Related Problems
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S $\subseteq$ V that maximizes the number of edges in the cut \delta(S) such that the induced graph G[S] is connected. We present the first non-trivial \Omega(1/log n) approximation algorithm for the connected maximum cut problem in general graphs using novel techniques. We then extend our algorithm to an edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in stark contrast to the classical max-cut problem, we show that the connected maximum cut problem remains NP-hard even on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the connected maximum cut problem on planar graphs and more generally on graphs with bounded genus.