Sahil Singla

105 papers A* 30A 6B 3Journal 57Unranked 8
YearRankTypeTitle / Venue / Authors
2025 J jnl
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders.
SIAM J. Comput.
Sepehr Assadi, Sahil Singla
2025 J jnl
Improved and Oracle-Efficient Online ℓ
CoRR
Rohan Ghuge, Vidya Muthukumar, Sahil Singla
2025 A* conf
Improved and Oracle-Efficient Online ℓ1-Multicalibration.
ICML
Rohan Ghuge, Vidya Muthukumar, Sahil Singla
2025 A* conf
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives.
FOCS
Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla
2025 J jnl
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives.
CoRR
Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla
2025 J jnl
Online Combinatorial Optimization with Graphical Dependencies.
CoRR
Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, Sahil Singla
2025 A* conf
Single-Sample and Robust Online Resource Allocation.
STOC
Rohan Ghuge, Sahil Singla, Yifan Wang
2025 J jnl
Single-Sample and Robust Online Resource Allocation.
CoRR
Rohan Ghuge, Sahil Singla, Yifan Wang
2024 A* conf
Bandit Algorithms for Prophet Inequality and Pandora's Box.
SODA
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, Yifan Wang
2024 A* conf
Bandit Sequential Posted Pricing via Half-Concavity.
EC
Sahil Singla, Yifan Wang
2024 A* conf
Improved Mechanisms and Prophet Inequalities for Graphical Dependencies.
EC
Vasilis Livanos, Kalen Patton, Sahil Singla
2024 J jnl
Improved Mechanisms and Prophet Inequalities for Graphical Dependencies.
CoRR
Vasilis Livanos, Kalen Patton, Sahil Singla
2024 A* conf
Online Combinatorial Allocations and Auctions with Few Samples.
FOCS
Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla
2024 J jnl
Online Combinatorial Allocations and Auctions with Few Samples.
CoRR
Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla
2024 J jnl
Prophet Secretary for Combinatorial Auctions and Matroids.
SIAM J. Comput.
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla
2024 A* conf
Sample Complexity of Posted Pricing for a Single Item.
NeurIPS
Billy Jin, Thomas Kesselheim, Will Ma, Sahil Singla
2024 J jnl
Sample Complexity of Posted Pricing for a Single Item.
CoRR
Billy Jin, Thomas Kesselheim, Will Ma, Sahil Singla
2024 A* conf
Supermodular Approximation of Norms and Applications.
STOC
Thomas Kesselheim, Marco Molinaro, Sahil Singla
2024 J jnl
Supermodular Approximation of Norms and Applications.
CoRR
Thomas Kesselheim, Marco Molinaro, Sahil Singla
2023 J jnl
Bandit Sequential Posted Pricing via Half-Concavity.
CoRR
Sahil Singla, Yifan Wang
2023 A* conf
Online and Bandit Algorithms Beyond ℓ
SODA
Thomas Kesselheim, Marco Molinaro, Sahil Singla
2023 J jnl
Prophet Inequalities with Linear Correlations and Augmentations.
ACM Trans. Economics and Comput.
Nicole Immorlica, Sahil Singla, Bo Waggoner
2023 A conf
Submodular Norms with Applications To Online Facility Location and Stochastic Probing.
APPROX/RANDOM
Kalen Patton, Matteo Russo, Sahil Singla
2023 J jnl
Submodular Norms with Applications To Online Facility Location and Stochastic Probing.
CoRR
Kalen Patton, Matteo Russo, Sahil Singla
2022 J jnl
Bandit Algorithms for Prophet Inequality and Pandora's Box.
CoRR
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, Yifan Wang
2022 A* conf
Online Discrepancy with Recourse for Vectors and Graphs.
SODA
Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla
2022 J jnl
Online and Bandit Algorithms Beyond 𝓁
CoRR
Thomas Kesselheim, Marco Molinaro, Sahil Singla
2022 A conf
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.
ITCS
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2022 A* conf
Robust Secretary and Prophet Algorithms for Packing Integer Programs.
SODA
C. J. Argue, Anupam Gupta, Marco Molinaro, Sahil Singla
2022 A* conf
Smoothed Analysis of the Komlós Conjecture.
ICALP
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2022 J jnl
Smoothed Analysis of the Komlós Conjecture.
CoRR
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2022 A conf
Submodular Dominance and Applications.
APPROX/RANDOM
Frederick Qiu, Sahil Singla
2022 J jnl
Submodular Dominance and Applications.
CoRR
Frederick Qiu, Sahil Singla
2021 — conf
Bag-Of-Tasks Scheduling on Related Machines.
APPROX-RANDOM
Anupam Gupta, Amit Kumar, Sahil Singla
2021 J jnl
Bag-of-Tasks Scheduling on Related Machines.
CoRR
Anupam Gupta, Amit Kumar, Sahil Singla
2021 A* conf
Efficient Approximation Schemes for Stochastic Probing and Prophet Problems.
EC
Danny Segev, Sahil Singla
2021 — conf
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem.
WINE
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, S. Matthew Weinberg
2021 J jnl
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem.
CoRR
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, S. Matthew Weinberg
2021 A* conf
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier.
SODA
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
2021 A* conf
Online Discrepancy Minimization for Stochastic Arrivals.
SODA
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2021 J jnl
Online Discrepancy with Recourse for Vectors and Graphs.
CoRR
Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla
2021 J jnl
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.
CoRR
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2021 J jnl
Robust Secretary and Prophet Algorithms for Packing Integer Programs.
CoRR
C. J. Argue, Anupam Gupta, Marco Molinaro, Sahil Singla
2021 J jnl
Some results on the spum and the integral spum of graphs.
Discret. Math.
Sahil Singla, Apurv Tiwari, Amitabha Tripathi
2020 A conf
Algorithms and Adaptivity Gaps for Stochastic k-TSP.
ITCS
Haotian Jiang, Jian Li, Daogao Liu, Sahil Singla
2020 J jnl
Efficient Approximation Schemes for Stochastic Probing and Prophet Problems.
CoRR
Danny Segev, Sahil Singla
2020 J jnl
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier.
CoRR
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
2020 J jnl
Improved truthful mechanisms for combinatorial auctions with submodular bidders.
SIGecom Exch.
Sepehr Assadi, Sahil Singla
2020 J jnl
Maximum Matching in the Online Batch-arrival Model.
ACM Trans. Algorithms
Euiwoong Lee, Sahil Singla
2020 — conf
Online Carpooling Using Expander Decompositions.
FSTTCS
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla
2020 J jnl
Online Carpooling using Expander Decompositions.
CoRR
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla
2020 J jnl
Online Discrepancy Minimization for Stochastic Arrivals.
CoRR
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2020 A* conf
Online Learning with Vector Costs and Bandits with Knapsacks.
COLT
Thomas Kesselheim, Sahil Singla
2020 J jnl
Online Learning with Vector Costs and Bandits with Knapsacks.
CoRR
Thomas Kesselheim, Sahil Singla
2020 A* conf
Online vector balancing and geometric discrepancy.
STOC
Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
2020 A* conf
Prophet Inequalities with Linear Correlations and Augmentations.
EC
Nicole Immorlica, Sahil Singla, Bo Waggoner
2020 J jnl
Prophet Inequalities with Linear Correlations and Augmentations.
CoRR
Nicole Immorlica, Sahil Singla, Bo Waggoner
2020 — ch.
Random-Order Models.
Beyond the Worst-Case Analysis of Algorithms
Anupam Gupta, Sahil Singla
2020 J jnl
Random-Order Models.
CoRR
Anupam Gupta, Sahil Singla
2020 A conf
Robust Algorithms for the Secretary Problem.
ITCS
Domagoj Bradac, Anupam Gupta, Sahil Singla, Goran Zuzic
2019 — conf
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing.
APPROX-RANDOM
Domagoj Bradac, Sahil Singla, Goran Zuzic
2019 J jnl
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing.
CoRR
Domagoj Bradac, Sahil Singla, Goran Zuzic
2019 J jnl
Algorithms and Adaptivity Gaps for Stochastic k-TSP.
CoRR
Haotian Jiang, Jian Li, Daogao Liu, Sahil Singla
2019 J jnl
Approximation Schemes for a Buyer with Independent Items via Symmetries.
CoRR
Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg
2019 A* conf
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries.
FOCS
Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg
2019 A* conf
Faster Matroid Intersection.
FOCS
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong
2019 J jnl
Faster Matroid Intersection.
CoRR
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong
2019 A* conf
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders.
FOCS
Sepehr Assadi, Sahil Singla
2019 J jnl
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders.
CoRR
Sepehr Assadi, Sahil Singla
2019 A* conf
Non-Clairvoyant Precedence Constrained Scheduling.
ICALP
Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla
2019 J jnl
Non-clairvoyant Precedence Constrained Scheduling.
CoRR
Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla
2019 J jnl
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization.
CoRR
Haotian Jiang, Janardhan Kulkarni, Sahil Singla
2019 J jnl
Online Vector Balancing and Geometric Discrepancy.
CoRR
Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
2019 — conf
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty.
APPROX-RANDOM
David Ellis Hershkowitz, R. Ravi, Sahil Singla
2019 J jnl
Robust Algorithms for the Secretary Problem.
CoRR
Domagoj Bradac, Anupam Gupta, Sahil Singla, Goran Zuzic
2019 B conf
The Markovian Price of Information.
IPCO
Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla
2019 J jnl
The Markovian Price of Information.
CoRR
Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla
2018 A conf
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities.
ESA
Euiwoong Lee, Sahil Singla
2018 J jnl
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities.
CoRR
Euiwoong Lee, Sahil Singla
2018 J jnl
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty.
CoRR
D. Ellis Hershkowitz, R. Ravi, Sahil Singla
2018 A* conf
Prophet Secretary for Combinatorial Auctions and Matroids.
SODA
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla
2018 A* conf
The Price of Information in Combinatorial Optimization.
SODA
Sahil Singla
2017 A* conf
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions.
SODA
Anupam Gupta, Viswanath Nagarajan, Sahil Singla
2017 A* conf
Combinatorial Prophet Inequalities.
SODA
Aviad Rubinstein, Sahil Singla
2017 J jnl
How to Morph Planar Graph Drawings.
SIAM J. Comput.
Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson
2017 B conf
Maximum Matching in the Online Batch-Arrival Model.
IPCO
Euiwoong Lee, Sahil Singla
2017 B conf
Online Matroid Intersection: Beating Half for Random Arrival.
IPCO
Guru Prashanth Guruganesh, Sahil Singla
2017 J jnl
Prophet Secretary for Combinatorial Auctions and Matroids.
CoRR
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla
2017 J jnl
The Price of Information in Combinatorial Optimization.
CoRR
Sahil Singla
2016 J jnl
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions.
CoRR
Anupam Gupta, Viswanath Nagarajan, Sahil Singla
2016 A* conf
Algorithms and Adaptivity Gaps for Stochastic Probing.
SODA
Anupam Gupta, Viswanath Nagarajan, Sahil Singla
2016 J jnl
Combinatorial Prophet Inequalities.
CoRR
Aviad Rubinstein, Sahil Singla
2016 J jnl
How to morph planar graph drawings.
CoRR
Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson
2016 J jnl
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy.
Math. Program.
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla
2015 J jnl
Online Matroid Intersection: Beating Half for Random Arrival.
CoRR
Guru Prashanth Guruganesh, Sahil Singla
2014 J jnl
Exact Analysis of TTL Cache Networks: The Case of Caching Policies driven by Stopping Times.
CoRR
Daniel S. Berger, Philipp Gland, Sahil Singla, Florin Ciucu
2014 J jnl
Exact analysis of TTL cache networks.
Perform. Evaluation
Daniel S. Berger, Philipp Gland, Sahil Singla, Florin Ciucu
2014 A* conf
Exact analysis of TTL cache networks: the case of caching policies driven by stopping times.
SIGMETRICS
Daniel S. Berger, Philipp Gland, Sahil Singla, Florin Ciucu
2014 J jnl
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy.
CoRR
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla
2013 J jnl
Battery provisioning and scheduling for a hybrid battery-diesel generator system.
SIGMETRICS Perform. Evaluation Rev.
Sahil Singla, Yashar Ghiassi-Farrokhfal, Srinivasan Keshav
2013 A* conf
Morphing Planar Graph Drawings with a Polynomial Number of Steps.
SODA
Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson
2013 — conf
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy.
ICALP (1)
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla
2012 — conf
Demand response through a temperature setpoint market in Ontario.
SmartGridComm
Sahil Singla, Srinivasan Keshav
2012 — conf
The impact of electricity pricing schemes on storage adoption in Ontario.
e-Energy
Tommy Carpenter, Sahil Singla, Parsiad Azimzadeh, Srinivasan Keshav
2010 J jnl
Exhaustive Verification of Weak Reconstruction For Self Complementary Graphs
CoRR
S. K. Gupta, Sahil Singla, Akash Khandelwal, Apurv Tiwari, Srilekha