Sahil Singla
Assistant Professor, School of Computer Science, Georgia Tech
Address: 2142 KACB, 266 Ferst Drive, Atlanta, GA 30332
Email: s <my last name> at gatech dot edu

Research Interests
My research is in Algorithms and Uncertainty where the goal is to design optimal algorithms for uncertain inputs by studying different forms of uncertainty together. My uncertainty models are inspired from areas such as Online Algorithms, Algorithmic Game Theory, Stochastic Optimization, Multi-Armed Bandits and Online Learning.

Here is my CV, DBLP, and Google Scholar. Also, a 3 min and a 1 hour video overview of my research.

Biography
I am an Assistant Professor in the School of Computer Science and a member of Algorithms & Randomness Center at Georgia Tech. Before coming to Atlanta, I was a Research Instructor (postdoc) at Princeton University and Institute for Advanced Study from 2018 to 2021. Earlier, I finished my PhD in Computer Science at Carnegie Mellon University where I was advised by Anupam Gupta and Manuel Blum.

Teachings and Tutorials

• Spring 2024, CS 6550/8803: Advanced Algorithms and Uncertainty, Georgia Tech
• Fall 2023, CS 3510: Design and Analysis of Algorithms, Georgia Tech
• Spring 2023, CS 3511: Algorithms Honors, Georgia Tech
• Spring 2022, CS 6550/8803: Advanced Algorithms and Uncertainty, Georgia Tech
• Tutorial (with videos) on Prophet Inequalities and Implications to Pricing Mechanisms and Online Algorithms at EC 2021
• Fall 2020, COS 521: Advanced Algorithm Design, Princeton
  
• Fall 2020, COS 397: IW Seminar on Algorithms and Uncertainty, Princeton
  
• Spring 2019, COS 445: Economics and Computation, Princeton
  
• Fall 2018, COS 397: IW Seminar on Algorithms and Uncertainty, Princeton
  

Postdocs and Ph.D. Students

• Rohan Ghuge (Postdoc, 2023-current)
• Kalen Patton (Ph.D., 2022-current)
• Yifan Wang (Ph.D., 2021-current)

Program Committees

• Symposium on Theory of Computing (STOC 2024)
• Symposium on Discrete Algorithms (SODA 2020, SODA 2023, SODA 2024)
• International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
• Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)
• Conference on Economics and Computation, Track Theory (EC 2019, EC 2020, EC 2021, EC 2023)
• EECS Rising Stars (RS 2023)
• The Web Conference, Track on Economics, Monetization, and Online Markets (TheWebConf 2022)
  
• International Colloquium on Automata Languages and Programming, Track A (ICALP 2021)
• Conference on Web and Internet Economics (WINE 2021)
• European Symposium on Algorithms, Track A (ESA 2019)
  

Selected Publications

Online Algorithms and Online Learning

• Supermodular Approximation of Norms and Applications
  T. Kesselheim, M. Molinaro, and S. Singla.
  Symposium on Theory of Computing (STOC 2024)
  
  
• 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)
  
  
• Random-Order Models
  A. Gupta and S. Singla.
  Chapter 11 in the book Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, 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
  
  

Algorithmic Game Theory

• 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)
  
  
• 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)
  
  
• Prophet Secretary for Combinatorial Auctions and Matroids
  S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla.
  Symposium on Discrete Algorithms (SODA 2018) (slides)
  
  

Stochastic Discrete Optimization

• Efficient Approximation Schemes for Stochastic Probing and Prophet Problems
  D. Segev and S. Singla.
  Conference on Economics and Computation (EC 2021) (video, 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)
  
  
• 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
  
  
• Exact Analysis of TTL Cache Networks
  D. Berger, P. Gland, S. Singla, and F. Ciucu.
  IFIP Performance 2014 (slides)
  Best Paper Award
  
  

Theses

• Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms
  S. Singla.
  Ph.D. Thesis, Carnegie Mellon University, 2018 (slides)
  
  
• On Using Storage and Genset for Mitigating Power Grid Failures
  S. Singla.
  M.Math Thesis, University of Waterloo, 2013 (slides)
  
  

Other Publications

• Bandit Sequential Posted Pricing via Half-Concavity
  S. Singla and Y. Wang.
  Working paper
  
  
• 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)
  
  
• Online Discrepancy Minimization for Stochastic Arrivals
  N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha.
  Symposium on Discrete Algorithms (SODA 2021) (video)
  
  
• 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)
  
  
• 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)
  
  
• 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)
  
  
• Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
  E. Lee and S. Singla.
  European Symposium on Algorithms (ESA 2018), Track A (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)
  
  
• Combinatorial Prophet Inequalities
  A. Rubinstein and S. Singla.
  Symposium on Discrete Algorithms (SODA 2017) (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
  
  
• 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

Other Presentations and Older Works

• Online Contention Resolution Schemes (OCRS)
  S. Singla.
  FOCS 2023 workshop on Online Algorithms and Online Rounding: Recent Progress (video, slides)
  
  
• 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