Sahil Singla

Sahil Singla

Auto-generated profile, based on publicly available information

Sahil Singla

Georgia Institute of Technology, Atlanta, USA

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
20 July 2020 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
ELEuiwoong Lee
Euiwoong Lee
SSSahil Singla
Sahil Singla
Consider a two-stage matching problem, where edges of an input graph are revealed in two stages (batches) and in each stage we have to immediately and irrevocably extend our matching using the edges from that stage. The natural greedy algorithm is half competitive. Even though there is a huge literature on online matching in adversarial vertex arrival model , no positive results were previously known in adversarial edge arrival model . For two-stage bipartite matching problem, we show that the optimal competitive ratio is exactly 2/3 in both the fractional and the randomized-integral models. Furthermore, our algorithm for fractional bipartite matching is instance optimal , i.e., it achieves the best competitive ratio for any given first stage graph. We also study natural extensions of this problem to general graphs and to s stages and present randomized-integral algorithms with competitive ratio ½ + 2− O(s) . Our algorithms use a novel Instance-Optimal-LP and combine graph decomposition techniques with online primal-dual analysis.

19 December 2023 in ACM Transactions on Economics and Computation
Verified
Journal Article
Open access
NINicole Immorlica
Nicole Immorlica
SSSahil Singla
Sahil Singla
BWBo Waggoner
Bo Waggoner
In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions) and decides when to stop the process by taking the current item. The goal is to prove a “prophet inequality”: that she can do approximately as well as a prophet with foreknowledge of all the values. In this work, we investigate this problem when the values are allowed to be correlated. Since nontrivial guarantees are impossible for arbitrary correlations, we consider a natural “linear” correlation structure introduced by Bateni et al. as a generalization of the common-base value model of Chawla et al. A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance for linear correlations. We relate this roadblock to another “augmentations” challenge that might be of independent interest: many existing prophet inequality algorithms are not robust to slight increases in the values of the arriving items. We leverage this intuition to prove bounds (matching up to constant factors) that decay gracefully with the amount of correlation of the arriving items. We extend these results to the case of selecting multiple items by designing a new (1+ o (1))-approximation ratio algorithm that is robust to augmentations.

5 February 2021 in Discrete Mathematics
Verified
Journal Article
Closed access
SSSahil Singla
Sahil Singla
ATApurv Tiwari
Apurv Tiwari
ATAmitabha Tripathi
Amitabha Tripathi

8 July 2024
Verified
Conference Paper
Open access
VLVasilis Livanos
Vasilis Livanos
KPKalen Patton
Kalen Patton
SSSahil Singla
Sahil Singla
Over the past two decades, significant strides have been made in stochastic problems such as revenue-optimal auction design and prophet inequalities, traditionally modeled with n independent random variables to represent the values of n items. However, in many applications, this assumption of independence often diverges from reality. Given the strong impossibility results associated with arbitrary correlations, recent research has pivoted towards exploring these problems under models of mild dependency. In this work, we study the optimal auction and prophet inequalities problems within the framework of the popular graphical model of Markov Random Fields (MRFs), a choice motivated by its ability to capture complex dependency structures. Specifically, for the problem of selling n items to a single buyer to maximize revenue, we show that max{SRev, BRev} is an O(Δ)-approximation to the optimal revenue for subadditive buyers, where Δ is the maximum weighted degree of the underlying MRF. This is a generalization as well as an exponential improvement on the exp(O(Δ))-approximation results of Cai and Oikonomou (EC 2021) for additive and unit-demand buyers. We also obtain a similar exponential improvement for the prophet inequality problem, which is asymptotically optimal as we show a matching upper bound.

8 July 2024
Verified
Conference Paper
Open access
SSSahil Singla
Sahil Singla
YWYifan Wang
Yifan Wang
Sequential posted pricing auctions are popular because of their simplicity in practice and their tractability in theory. A usual assumption in their study is that the Bayesian prior distributions of the buyers are known to the seller, while in reality these priors can only be accessed from historical data. To overcome this assumption, we study sequential posted pricing in the bandit learning model, where the seller interacts with n buyers over T rounds: In each round the seller posts n prices for the n buyers and the first buyer with a valuation higher than the price takes the item. The only feedback that the seller receives in each round is the revenue. Our main results obtain nearly-optimal regret bounds for single-item sequential posted pricing in the bandit learning model. In particular, we achieve an [EQUATION] regret for buyers with (Myerson's) regular distributions and an Õ(poly(n)T2/3) regret for buyers with general distributions, both of which are tight in the number of rounds T. Our result for regular distributions was previously not known even for the single-buyer setting and relies on a new half-concavity property of the revenue function in the value space. For n sequential buyers, our technique is to run a generalized single-buyer algorithm for all the buyers and to carefully bound the regret from the sub-optimal pricing of the suffix buyers. The full version of the paper is available at https://arxiv.org/abs/2312.12794.

10 June 2024
Verified
Conference Paper
Open access
TKThomas Kesselheim
Thomas Kesselheim
MMMarco Molinaro
Marco Molinaro
SSSahil Singla
Sahil Singla
Many classical problems in theoretical computer science involve norms, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The last decade has seen a lot of interest in designing algorithms beyond the standard ℓp norms ||· ||p. Despite notable advancements, many existing methods remain tailored to specific problems, leaving a broader applicability to general norms less understood. This paper investigates the intrinsic properties of ℓp norms that facilitate their widespread use and seeks to abstract these qualities to a more general setting. We identify supermodularity—often reserved for combinatorial set functions and characterized by monotone gradients—as a defining feature beneficial for ||·||pp. We introduce the notion of p-supermodularity for norms, asserting that a norm is p-supermodular if its pth power function exhibits supermodularity. The association of supermodularity with norms offers a new lens through which to view and construct algorithms. Our work demonstrates that for a large class of problems p-supermodularity is a sufficient criterion for developing good algorithms. This is either by reframing existing algorithms for problems like Online Load-Balancing and Bandits with Knapsacks through a supermodular lens, or by introducing novel analyses for problems such as Online Covering, Online Packing, and Stochastic Probing. Moreover, we prove that every symmetric norm can be approximated by a p-supermodular norm. Together, these recover and extend several existing results, and support p-supermodularity as a unified theoretical framework for optimization challenges centered around norm-related problems.