About

Anupam Gupta is a faculty member in the Theoretical Computer Science Group at New York University. His research focuses on algorithms, specifically in the areas of approximation algorithms, online algorithms, and metric embeddings. As part of a group that applies mathematical tools to various disciplines within computer science, his work contributes to advancing the understanding and development of efficient algorithmic solutions. The group at NYU is engaged in a broad range of theoretical computer science topics, including security, systems, and computational geometry, situating Gupta's research within a vibrant and interdisciplinary academic environment.

Research topics

• Computer Science
• Algorithm
• Machine Learning
• Mathematics
• Political Science
• Sociology
• Law
• Artificial Intelligence
• Combinatorics
• Discrete mathematics
• Statistics
• Programming language
• Operations research
• Engineering
• Mathematical optimization

Selected publications

• Power consumption prediction using machine learning

  AIP conference proceedings · 2025-01-01

  article
  PublisherDOI

• Pairwise-independent contention resolution

  Mathematical Programming · 2025-07-10

  articleOpen access1st authorCorresponding

  Abstract We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a $$(1-o_k(1))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:msub> <mml:mi>o</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -selectable OCRS for uniform matroids of rank k , and $$\Omega (1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -selectable OCRSes for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [2] showing that no $$\omega (1/k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ω</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -selectable OCRS exists in the PI setting for general matroids of rank k .

  PublisherOA PDFDOI

• Tight Results for Online Convex Paging

  2025-06-15

  article1st authorCorresponding
  PublisherDOI

• Complexity of Local Search for CSPs Parameterized by Constraint Difference

  ArXiv.org · 2025-12-02

  preprintOpen access

  In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset $S$ of a universe $U$, the new input consists of a current solution $P$ (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution $S^*$, the goal is to find a feasible solution as good as $S^*$ in parameterized time $f(k) \cdot n^{O(1)}$, where $k$ denotes the distance $|PΔS^*|$. This model generalizes numerous classical parameterized optimization problems whose parameter $k$ is the minimum number of elements removed from $U$ to make it feasible, which corresponds to the case $P = U$. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where $U$ is the set of constraints, and a subset $U'$ of constraints is feasible if there is an assignment to the variables satisfying all constraints in $U'$. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate's acceptance depends on the number of true literals.

  PublisherOA PDFDOI

• Multi-Platform Autobidding with and without Predictions

  ArXiv.org · 2025-02-26

  preprintOpen access

  We study the problem of finding the optimal bidding strategy for an advertiser in a multi-platform auction setting. The competition on a platform is captured by a value and a cost function, mapping bidding strategies to value and cost respectively. We assume a diminishing returns property, whereby the marginal cost is increasing in value. The advertiser uses an autobidder that selects a bidding strategy for each platform, aiming to maximize total value subject to budget and return-on-spend constraint. The advertiser has no prior information and learns about the value and cost functions by querying a platform with a specific bidding strategy. Our goal is to design algorithms that find the optimal bidding strategy with a small number of queries. We first present an algorithm that requires \(O(m \log (mn) \log n)\) queries, where $m$ is the number of platforms and $n$ is the number of possible bidding strategies in each platform. Moreover, we adopt the learning-augmented framework and propose an algorithm that utilizes a (possibly erroneous) prediction of the optimal bidding strategy. We provide a $O(m \log (mη) \log η)$ query-complexity bound on our algorithm as a function of the prediction error $η$. This guarantee gracefully degrades to \(O(m \log (mn) \log n)\). This achieves a ``best-of-both-worlds'' scenario: \(O(m)\) queries when given a correct prediction, and \(O(m \log (mn) \log n)\) even for an arbitrary incorrect prediction.

  PublisherOA PDFDOI

• Multi-Platform Autobidding with and without Predictions

  2025-04-22

  articleOpen access

  We study the problem of finding the optimal bidding strategy for an advertiser in a multi-platform auction setting. The competition on a platform is captured by a value and a cost function, mapping bidding strategies to value and cost respectively. We assume a diminishing returns property, whereby the marginal cost is increasing in value. The advertiser uses an autobidder that selects a bidding strategy for each platform, aiming to maximize total value subject to budget and return-on-spend constraint. The advertiser has no prior information and learns about the value and cost functions by querying a platform with a specific bidding strategy. Our goal is to design algorithms that find the optimal bidding strategy with a small number of queries.

  PublisherOA PDFDOI

• The Online Submodular Cover Problem

  ArXiv.org · 2025-10-10

  preprintOpen access1st authorCorresponding

  In the submodular cover problem, we are given a monotone submodular function $f$, and we want to pick the min-cost set $S$ such that $f(S) = f(N)$. Motivated by problems in network monitoring and resource allocation, we consider the submodular cover problem in an online setting. As a concrete example, suppose at each time $t$, a nonnegative monotone submodular function $g_t$ is given to us. We define $f^{(t)} = \sum_{s \leq t} g_s$ as the sum of all functions seen so far. We need to maintain a submodular cover of these submodular functions $f^{(1)}, f^{(2)}, \ldots f^{(T)}$ in an online fashion; i.e., we cannot revoke previous choices. Formally, at each time $t$ we produce a set $S_t \subseteq N$ such that $f^{(t)}(S_t) = f^{(t)}(N)$ -- i.e., this set $S_t$ is a cover -- such that $S_{t-1} \subseteq S_t$, so previously decisions to pick elements cannot be revoked. (We actually allow more general sequences $\{f^{(t)}\}$ of submodular functions, but this sum-of-simpler-submodular-functions case is useful for concreteness.) We give polylogarithmic competitive algorithms for this online submodular cover problem. The competitive ratio on an input sequence of length $T$ is $O(\ln n \ln (T \cdot f(N) / f_{\text{min}}))$, where $f_{\text{min}}$ is the smallest nonzero marginal for functions $f^{(t)}$, and $|N| = n$. For the special case of online set cover, our competitive ratio matches that of Alon et al. [SIAM J. Comp. 03], which are best possible for polynomial-time online algorithms unless $NP \subseteq BPP$ (see Korman 04). Since existing offline algorithms for submodular cover are based on greedy approaches which seem difficult to implement online, the technical challenge is to (approximately) solve the exponential-sized linear programming relaxation for submodular cover, and to round it, both in the online setting.

  PublisherOA PDFDOI

• Structural iterative rounding for generalized k-median problems

  Mathematical Programming · 2024-07-10 · 5 citations

  articleOpen access1st authorCorresponding

  Abstract This paper considers approximation algorithms for generalized k -median problems. These problems can be informally described as k -median with a constant number of extra constraints, and includes k -median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized k -median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for k -median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for k -median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios $$6.994 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6.994</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> and $$6.387 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6.387</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> for k -median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio $$7.081 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>7.081</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018).

  PublisherOA PDFDOI

• Power Consumption Prediction Using Machine Learning

  Journal of Machine Learning and Deep Learning · 2024-12-31

  article

  Energy is vital in the modern world, and resource management depends on our ability to estimate our energy consumption with enough accuracy. The goal of our initiative is to alter the way we utilize electricity. Its primary objectives are to ensure that invoices are correct, promote energy conservation, enhance billing transparency, and assist in forecasting future energy requirements. We want to tackle typical issues such as incorrect billing, insufficient real-time data, complex data patterns, and privacy concerns. Our work focuses on power consumption prediction through machine learning. Our model powered by LSTM algorithms tries to forecast how much energy we will use in the future by utilizing historical usage data and other variables. By doing so, we can more effectively use resources, distribute and manage energy, and advance sustainability.

  PublisherDOI

• Early Fusion of Features for Semantic Segmentation

  arXiv (Cornell University) · 2024-02-08

  preprintOpen access1st authorCorresponding

  This paper introduces a novel segmentation framework that integrates a classifier network with a reverse HRNet architecture for efficient image segmentation. Our approach utilizes a ResNet-50 backbone, pretrained in a semi-supervised manner, to generate feature maps at various scales. These maps are then processed by a reverse HRNet, which is adapted to handle varying channel dimensions through 1x1 convolutions, to produce the final segmentation output. We strategically avoid fine-tuning the backbone network to minimize memory consumption during training. Our methodology is rigorously tested across several benchmark datasets including Mapillary Vistas, Cityscapes, CamVid, COCO, and PASCAL-VOC2012, employing metrics such as pixel accuracy and mean Intersection over Union (mIoU) to evaluate segmentation performance. The results demonstrate the effectiveness of our proposed model in achieving high segmentation accuracy, indicating its potential for various applications in image analysis. By leveraging the strengths of both the ResNet-50 and reverse HRNet within a unified framework, we present a robust solution to the challenges of image segmentation.

  PublisherOA PDFDOI

Recent grants

• AF: Small: Future Directions in Approximation Algorithms Research

  NSF · $415k · 2010–2015

• BSF: 2014414: New Challenges and Perspectives in Online Algorithms

  NSF · $40k · 2015–2019

• AF: Small: New Approaches for Approximation and Online Algorithms

  NSF · $300k · 2019–2021

• Collaborative Research: AF: Small: Combinatorial Optimization for Stochastic Inputs

  NSF · $250k · 2020–2023

• AF: Small: Approximation Algorithms for Uncertain Environments and Graph Partitioning

  NSF · $406k · 2013–2017

Frequent coauthors

• Amit Kumar

  Intel (India)

  95 shared

• Viswanath Nagarajan

  Karpagam Academy of Higher Education

  61 shared

• Ravishankar Krishnaswamy

  Microsoft Research (India)

  59 shared

• Sahil Singla

  48 shared

• R. Ravi

  41 shared

• Kunal Talwar

  40 shared

• Jason Li

  33 shared

• Euiwoong Lee

  28 shared

Labs

• Theoretical Computer Science at NYUPI

  Applying mathematical tools to a variety of disciplines in computer science

Education

• Ph.D.

  University of California, Berkeley

  2000

• Other

  Indian Institute of Technology, Kanpur

  1996

Awards & honors

• Herb Simon Award for Teaching Excellence at Carnegie Mellon
• ACM Fellow in 2021