All Publications (Selected Publications)

• Online Algorithms via Minimax and Posterior Matching
  T. Kesselheim, M. Molinaro, K. Patton, and S. Singla.
  Symposium on Foundations of Computer Science (FOCS 2026)
  
  
• Online Graph Balancing and the Power of Two Choices
  N. Bansal, M. Prabhu, S. Singla, and S. Sundaram.
  Symposium on Foundations of Computer Science (FOCS 2026)
  
  
• Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
  A. Rubinstein and S. Singla.
  Symposium on Theory of Computing (STOC 2026) (video)
  
  
• Online Combinatorial Optimization with Graphical Dependencies
  Z. Gao, E. Gergatsouli, K. Patton, and S. Singla.
  Symposium on Theory of Computing (STOC 2026) (video)
  
  
• Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
  T. Kesselheim, M. Molinaro, K. Patton, and S. Singla.
  Symposium on Foundations of Computer Science (FOCS 2025)
  
  
• Improved and Oracle-Efficient Online l_1 Multicalibration
  R. Ghuge, V. Muthukumar, and S. Singla.
  International Conference on Machine Learning (ICML 2025)
  
  
• Single-Sample and Robust Online Resource Allocation
  R. Ghuge, S. Singla, and Y. Wang.
  Symposium on Theory of Computing (STOC 2025) (video)
  
  
• Online Combinatorial Allocations and Auctions with Few Samples
  P. Duetting, T. Kesselheim, B. Lucier, R. Reiffenhauser, and S. Singla.
  Symposium on Foundations of Computer Science (FOCS 2024) (video)
  
  
• Supermodular Approximation of Norms and Applications
  T. Kesselheim, M. Molinaro, and S. Singla.
  Symposium on Theory of Computing (STOC 2024) (video)
  
  
• Sample Complexity of Posted Pricing for a Single Item
  B. Jin, T. Kesselheim, W. Ma, and S. Singla.
  Neural Information Processing Systems (NeurIPS 2024)
  Spotlight at NeurIPS
  
  
• Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
  V. Livanos, K. Patton, and S. Singla.
  Conference on Economics and Computation (EC 2024) (video)
  
  
• Bandit Sequential Posted Pricing via Half-Concavity
  S. Singla and Y. Wang.
  Conference on Economics and Computation (EC 2024) (video)
  
  
• Bandit Algorithms for Prophet Inequality and Pandora's Box
  K. Gatmiry, T. Kesselheim, S. Singla, and Y. Wang.
  Symposium on Discrete Algorithms (SODA 2024) (slides)
  
  
• Online and Bandit Algorithms Beyond L_p Norms
  T. Kesselheim, M. Molinaro, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2023) (slides)
  
  
• Submodular Norms with Applications to Online Facility Location and Stochastic Probing
  K. Patton, M. Russo, and S. Singla.
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2023)
  
  
• Smoothed Analysis of the Komlos Conjecture
  N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha.
  International Colloquium on Automata, Languages and Programming (ICALP 2022)
  
  
• Submodular Dominance and Applications
  F. Qiu and S. Singla.
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2022) (video)
  
  
• Online Discrepancy with Recourse for Vectors and Graphs
  A. Gupta, V. Gurunathan, R. Krishnaswamy, A. Kumar, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2022) (video, slides)
  
  
• Robust Secretary and Prophet Algorithms for Packing Integer Problems
  C. J. Argue, A. Gupta, M. Molinaro, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2022) (video, slides)
  
  
• Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
  N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha.
  Innovations in Theoretical Computer Science (ITCS 2022) (video)
  
  
• Random-Order Models
  A. Gupta and S. Singla.
  Chapter 11 in the book Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, 2021
  
  
• Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
  S. Assadi, T. Kesselheim, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2021) (video, slides)
  
  
• Online Discrepancy Minimization for Stochastic Arrivals
  N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha.
  Symposium on Discrete Algorithms (SODA 2021) (video)
  
  
• Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
  D. Segev and S. Singla.
  Conference on Economics and Computation (EC 2021) (video, slides)
  Mathematics of Operations Research (MOR 2025)
  
  
• Bag-of-Tasks Scheduling on Related Machines
  A. Gupta, A. Kumar, and S. Singla.
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2021) (video)
  
  
• Some Results on the Spum and the Integral Spum of Graphs
  S. Singla, A. Tiwari, and A. Tripathi.
  Discrete Mathematics 2021 (most work done in 2011 as an undergrad)
  
  
• Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
  M. Bahrani, H. Beyhaghi, S. Singla, and S. M. Weinberg.
  Conference on Web and Internet Economics (WINE 2021)
  
  
• Online Vector Balancing and Geometric Discrepancy
  N. Bansal, H. Jiang, S. Singla, and M. Sinha.
  Symposium on Theory of Computing (STOC 2020) (video, slides)
  Contributed talk at HALG 2020
  Invited talk at TCS+ 2020
  (also see below the paper Online Discrepancy Minimization for Stochastic Arrivals)
  
  
• Online Learning with Vector Costs and Bandits with Knapsacks
  T. Kesselheim and S. Singla.
  Conference on Learning Theory (COLT 2020) (video, slides)
  Contributed talk at HALG 2020
  
  
• Prophet Inequalities with Linear Correlations and Augmentations
  N. Immorlica, S. Singla, and B. Waggoner.
  Conference on Economics and Computation (EC 2020) (video, slides)
  Talk at INFORMS Annual Meeting 2020 (video)
  ACM Transactions on Economics and Computation (TEAC)
  
  
• Robust Algorithms for the Secretary Problem
  D. Bradac, A. Gupta, S. Singla, and G. Zuzic.
  Innovations in Theoretical Computer Science (ITCS 2020) (video, slides)
  Contributed talk at HALG 2020
  
  
• Algorithms and Adaptivity Gaps for Stochastic k-TSP
  H. Jiang, J. Li, D. Liu, and S. Singla.
  Innovations in Theoretical Computer Science (ITCS 2020) (video)
  Contributed talk at HALG 2020
  
  
• Online Carpooling using Expander Decompositions
  A. Gupta, R. Krishnaswamy, A. Kumar, and S. Singla.
  Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) (video)
  
  
• Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
  P. Kothari, D. Mohan, A. Schvartzman, S. Singla, and S. M. Weinberg.
  Symposium on Foundations of Computer Science (FOCS 2019) (video, slides)
  Invited talk at HALG 2020 (video)
  
  
• Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
  S. Assadi and S. Singla.
  Symposium on Foundations of Computer Science (FOCS 2019) (video, slides)
  Short research note in SIGecom Exchanges
  Invited to SICOMP Special Issue for FOCS 2019
  Invited talk at Highlights Beyond EC at EC 2020 (video)
  
  
• Faster Matroid Intersection
  D. Chakrabarty, Y. T. Lee, A. Sidford, S. Singla, and S. C. Wong.
  Symposium on Foundations of Computer Science (FOCS 2019) (video)
  Invited talk at HALG 2020 (video)
  
  
• Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
  H. Jiang, J. Kulkarni, and S. Singla.
  Manuscript 2019 (video, slides)
  
  
• (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
  D. Bradac, S. Singla, and G. Zuzic.
  International Conference on Randomization and Computation (RANDOM 2019) (slides)
  
  
• Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
  D. E. Hershkowitz, R. Ravi, and S. Singla.
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2019)
  
  
• Non-clairvoyant Precedence Constrained Scheduling
  N. Garg, A. Gupta, A. Kumar, and S. Singla.
  International Colloquium on Automata, Languages and Programming (ICALP 2019), Track A (slides)
  
  
• The Markovian Price of Information
  A. Gupta, H. Jiang, Z. Scully, and S. Singla.
  Integer Programming and Combinatorial Optimization (IPCO 2019) (slides)
  
  
• Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms
  S. Singla.
  Ph.D. Thesis, Carnegie Mellon University, 2018 (slides)
  
  
• The Price of Information in Combinatorial Optimization
  S. Singla.
  Symposium on Discrete Algorithms (SODA 2018) (slides)
  (also see below the paper The Markovian Price of Information)
  
  
• Prophet Secretary for Combinatorial Auctions and Matroids
  S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2018) (slides)
  SIAM Journal on Computing (SICOMP 2024)
  
  
• Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
  E. Lee and S. Singla.
  European Symposium on Algorithms (ESA 2018), Track A (slides)
  
  
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
  A. Gupta, V. Nagarajan, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2017) (video, slides)
  Invited talk at ISMP 2018
  
  
• Combinatorial Prophet Inequalities
  A. Rubinstein and S. Singla.
  Symposium on Discrete Algorithms (SODA 2017) (slides)
  
  
• Maximum Matching in the Online Batch-Arrival Model
  E. Lee and S. Singla.
  Prelim. version in Integer Programming and Combinatorial Optimization (IPCO 2017) (video, slides)
  ACM Transactions on Algorithms (TALG 2020)
  
  
• Online Matroid Intersection: Beating half for Random Arrival
  G. Guruganesh and S. Singla.
  Integer Programming and Combinatorial Optimization (IPCO 2017) (video, slides)
  
  
• Algorithms and Adaptivity Gaps for Stochastic Probing
  A. Gupta, V. Nagarajan, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2016) (video, slides)
  
  
• Using Storage to Minimize Carbon Footprint of Diesel Generators for Unreliable Grids
  S. Singla, Y. Ghiassi-Farrokhfal, and S. Keshav.
  IEEE Transactions on Sustainable Energy 2014
  
  
• How to Morph Planar Graph Drawings
  S. Alamdari, P. Angelini, F. Barrera-Cruz, T. M. Chan, G. D. Lozzo, G. D. Battista, F. Frati, P. Haxell, A. Lubiw, M. Patrignani, V. Roselli, S. Singla, and B. T. Wilkinson.
  Prelim. version in Symposium on Discrete Algorithms (SODA 2013)
  SIAM Journal on Computing (SICOMP 2017)
  
  
• On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
  J. Cheriyan, Z. Gao, K. Georgiou, and S. Singla.
  Prelim. version in International Colloquium on Automata, Languages and Programming (ICALP 2013), Track A
  Mathematical Programming (MAPR 2016), Series A
  
  
• On Using Storage and Genset for Mitigating Power Grid Failures
  S. Singla.
  M.Math Thesis, University of Waterloo, 2013 (slides)
  
  
• Battery Provisioning and Scheduling for a Hybrid Battery-Diesel Generator System
  S. Singla, Y. Ghiassi-Farrokhfal, and S. Keshav.
  SIGMETRICS Performance Evaluation Review (PER 2013)
  
  
• Demand Response through a Temperature Setpoint Market in Ontario
  S. Singla and S. Keshav.
  IEEE SmartGridComm 2012
  
  
• The Impact of Electricity Pricing Schemes on Storage Integration In Ontario
  T. Carpenter, S. Singla, P. Azimzadeh, and S. Keshav.
  ACM e-Energy 2012
  
  

Working Papers

• Philosopher and Prophet Inequalities for Divisible Items
  T. Oliveira, M. Singh, and S. Singla.
  Working paper
  
  
• Adversarial Online Classification with a Preview
  R. Livni and S. Singla.
  Working paper (video)
  
  
• Efficient Algorithms for Online Subadditive Combinatorial Allocations
  C. MacRury, R. Neogi, S. Singla, S. M. Sundaram, and C. Swamy.
  Working paper
  
  
• Online Allocation Using Few Samples
  M. Faw, S. Singla, and Y. Wang.
  Working paper
  
  
• Improved Combinatorial Auctions with and without Samples
  A. Rubinstein and S. Singla.
  Working paper
  
  

Other Presentations and Older Works

• Discrete Optimization under Uncertainty.
  S. Singla.
  IAS, October 2019 (video, slides)
  
  
• Probing Algorithms for Combinatorial Optimization Under Uncertainty
  S. Singla.
  Princeton 2017, China Theory Week 2017, MSR New England 2018, and Rutgers 2018 (slides)
  
  
• Steiner Trees and Steiner Forests
  A. Garg, A. Goel, and S. Singla.
  B.Tech. Thesis 2011, IIT Delhi
  
  
• Design and Implementation of a News Reader based on Social Networks
  A. Uppal, S. K. Gupta, and S. Singla.
  Project Report 2011, IIT Delhi
  
  
• Exhaustive Verification of Weak Reconstruction for Self Complementary graphs
  S. K. Gupta, S. Singla, A. Khandelwal, A. Tiwari, and Srilekha.
  Poster at ICM 2010's satellite conference, ICRTGC 2010