Princeton University and Institute for Advanced Study

Address: 194 Nassau Street, Room 219, Princeton, NJ 08542

Email: <my last name> at cs dot princeton dot edu

For a "general audience" talk of some of my research, see this video.

I am a Research Instructor (postdoc) at Princeton University and the Institute for Advanced Study. Before coming to Princeton, I finished my PhD in Computer Science at Carnegie Mellon University under the supervision of Prof Manuel Blum and Prof Anupam Gupta. Earlier, I obtained a master's degree from University of Waterloo and a bachelor's degree from Indian Institute of Technology, Delhi, in Computer Science.

- Symposium on Discrete Algorithms (SODA 2020)

- Economics and Computation (EC 2019, EC 2020)

- European Symposium on Algorithms (ESA 2019 Track A)

- 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.

- A. Gupta and S. Singla. `Random-Order Models', Chapter 11 in `Beyond the Worst-Case Analysis of Algorithms', Cambridge University Press, 2020.

- S. Singla. `Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms'. Ph.D. Thesis, Carnegie Mellon University, August 2018. (slides)

- T. Kesselheim and S. Singla. `Online Learning with Vector Costs and Bandits with Knapsacks'. Under Submission.

- N. Immorlica, S. Singla, and B. Waggoner. `Prophet Inequalities with Linear Correlations and Augmentations'. Preprint.

- N. Bansal, H. Jiang, S. Singla, and M. Sinha. `Online Vector Balancing and Geometric Discrepancy'. ACM Symposium on Theory of Computing
**(STOC)**, June 2020. (slides)

- H. Jiang, J. Li, D. Liu, and S. Singla. `Algorithms and Adaptivity Gaps for Stochastic k-TSP'. Innovations in Theoretical Computer Science
**(ITCS)**, January 2020. (video)

- D. Bradac, A. Gupta, S. Singla, and G. Zuzic. `Robust Algorithms for the Secretary Problem'. Innovations in Theoretical Computer Science
**(ITCS)**, January 2020. (video, slides)

- S. Assadi and S. Singla. `Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders'. IEEE Symposium on Foundations of Computer Science
**(FOCS)**, November 2019. (video, slides) (**Invited to Special Issue of SICOMP**)

- D. Chakrabarty, Y. T. Lee, A. Sidford, S. Singla, and S. C. Wong. `Faster Matroid Intersection'. IEEE Symposium on Foundations of Computer Science
**(FOCS)**, November 2019. (video) (**Invited talk at HALG 2020**)

- P. Kothari, D. Mohan, A. Schvartzman, S. Singla, and S. M. Weinberg. `Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries'. IEEE Symposium on
Foundations of Computer Science
**(FOCS)**, November 2019. (video, slides) (**Invited talk at HALG 2020**)

- H. Jiang, J. Kulkarni, and S. Singla. `Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization'. October 2019. (slides)

- D. Bradac, S. Singla, and G. Zuzic. `(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing'. International Conference on Randomization and Computation
**(RANDOM)**, September 2019. (slides)

- D. E. Hershkowitz, R. Ravi, and S. Singla. `Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty'. International Conference on Approximation Algorithms for Combinatorial Optimization Problems
**(APPROX)**, September 2019.

- N. Garg, A. Gupta, A. Kumar, and S. Singla. `Non-clairvoyant Precedence Constrained Scheduling'. International Colloquium on Automata, Languages and Programming
**(ICALP)**, Track A, July 2019. (slides)

- A. Gupta, H. Jiang, Z. Scully, and S. Singla. `The Markovian Price of Information'. Integer Programming and Combinatorial Optimization
**(IPCO)**, May 2019. (slides)

- E. Lee and S. Singla. `Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities'. European Symposium on Algorithms
**(ESA)**, Track A, August 2018. (slides)

- S. Singla. `The Price of Information in Combinatorial Optimization'. ACM-SIAM Symposium on Discrete Algorithms
**(SODA)**, January 2018. (slides)

- S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla. `Prophet Secretary for Combinatorial Auctions and Matroids'. ACM-SIAM Symposium on Discrete Algorithms
**(SODA)**, January 2018. (slides)

- E. Lee and S. Singla. `Maximum Matching in the Online Batch-Arrival Model'. Integer Programming and Combinatorial Optimization (
**IPCO)**, June 2017. (video, slides)

- G. Guruganesh and S. Singla. `Online Matroid Intersection: Beating half for Random Arrival'. Integer Programming and Combinatorial Optimization
**(IPCO)**, June 2017. (video, slides)

- A. Gupta, V. Nagarajan, and S. Singla. `Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions'. ACM-SIAM Symposium on Discrete Algorithms
**(SODA)**, January 2017. (video, slides)

- A. Rubinstein and S. Singla. `Combinatorial Prophet Inequalities'. ACM-SIAM Symposium on Discrete Algorithms
**(SODA)**, January 2017. (slides)

- 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, B. T. Wilkinson. `How to Morph Planar Graph Drawings'. SIAM Journal on Computing
**(SICOMP)**, 46 (2), Pg. 824-852, 2017. (Prelim. version in**SODA**, January 2013.)

- A. Gupta, V. Nagarajan, and S. Singla. `Algorithms and Adaptivity Gaps for Stochastic Probing'. ACM-SIAM Symposium on Discrete Algorithms
**(SODA)**, January 2016. (video, slides)

- J. Cheriyan, Z. Gao, K. Georgiou, and S. Singla. `On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy'. Mathematical Programming, Series A, Springer Berlin Heidelberg, ISSN 0025-5610, Pg. 1-29, 2016. (Prelim. version in
**ICALP**, Track A, July 2013.)

- D. Berger, P. Gland, S. Singla, and F. Ciucu. `Exact Analysis of TTL Cache Networks'. IFIP Performance, October 2014. (slides)
**(Best Paper Award)**

- S. Singla, Y. Ghiassi-Farrokhfal, and S. Keshav. `Using Storage to Minimize Carbon Footprint of
Diesel Generators for Unreliable Grids'. IEEE Transactions on Sustainable Energy, October 2014.

- S. Singla, Y. Ghiassi-Farrokhfal, and S. Keshav. `Battery Provisioning and Scheduling for a Hybrid Battery-Diesel Generator System'. SIGMETRICS Performance Evaluation Review, 41(3), 2013.

- S. Singla and S. Keshav. `Demand Response through a Temperature Setpoint Market in Ontario'. IEEE SmartGridComm, November 2012.

- T. Carpenter, S. Singla, P. Azimzadeh, and S. Keshav. `The Impact of Electricity Pricing Schemes on Storage Integration In Ontario'. ACM e-Energy, May 2012.

- S. Singla. `Discrete Optimization under Uncertainty'. IAS, October 2019. (slides, video)

- S. Singla. `Probing Algorithms for Combinatorial Optimization Under Uncertainty'. Princeton 2017, China Theory Week 2017, and MSR New England 2018. (slides)

- S. Singla. `On Using Storage and Genset for Mitigating Power Grid Failures'. M.Math Thesis, University of Waterloo, April 2013. (slides)

- S. Singla, A. Tiwari, and A. Tripathi. `On the Spum and the Integral Spum of Graphs'. Manuscript.

- S. Singla. `The School Bus and the Orienteering problem'. Course Project Report, CO754, Univ. Waterloo, Winter 2012.

- A. Garg, A. Goel, and S. Singla. `Steiner Trees and Steiner Forests' . B.Tech Thesis, IIT-Delhi, May 2011.

- A. Uppal, S. K. Gupta, and S. Singla. `Design and Implementation of a News Reader based on Social Networks'. Project Report, IIT-Delhi, May 2011.

- S. K. Gupta, S. Singla, A. Khandelwal, A. Tiwari, and Srilekha. `Exhaustive Verification of Weak Reconstruction for Self Complementary graphs'. Poster at ICM 2010's satellite conference, ICRTGC, Aug 2010.