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

Broadly, I am interested in theoretical problems related to the theme `Algorithms and Uncertainty'. More particularly, I am currently working on discrete optimization problems and my uncertainty models are inspired from areas such as Online Algorithms, Algorithmic Game Theory, Stochastic Optimization, Multi-Armed Bandits and Online Learning.

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 where I was advised by Manuel Blum and Anupam Gupta. Earlier, I got a master's degree from University of Waterloo and a bachelor's degree from Indian Institute of Technology, Delhi, in Computer Science.

- International Colloquium on Automata Languages and Programming, Track A (ICALP 2021)
- Symposium on Discrete Algorithms (SODA 2020)
- Conference on Economics and Computation, Track Theory (EC 2019, EC 2020)
- European Symposium on Algorithms, Track A (ESA 2019)

- 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

- Random-Order Models

A. Gupta and S. Singla.

Chapter 11 in**Beyond the Worst-Case Analysis of Algorithms**, Cambridge University Press, 2020 (book)

- Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms

S. Singla.

**Ph.D. Thesis**, Carnegie Mellon University, 2018 (slides)

- Efficient Approximation Schemes for Stochastic Probing and Prophet Problems

D. Segev and S. Singla.

Manuscript 2020

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

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

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

- 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)**

- The Price of Information in Combinatorial Optimization

S. Singla.

Symposium on Discrete Algorithms**(SODA 2018)**(slides)

- Prophet Secretary for Combinatorial Auctions and Matroids

S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla.

Symposium on Discrete Algorithms**(SODA 2018)**(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**

- Exact Analysis of TTL Cache Networks

D. Berger, P. Gland, S. Singla, and F. Ciucu.

IFIP**Performance 2014**(slides)

**Best Paper Award**

- Online Discrepancy Minimization for Stochastic Arrivals

N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha.

Manuscript 2020

- Prophet Inequalities with Linear Correlations and Augmentations

N. Immorlica, S. Singla, and B. Waggoner.

Conference on Economics and Computation**(EC 2020)**(video, slides)

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

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

- Online Carpooling using Expander Decompositions

A. Gupta, R. Krishnaswamy, A. Kumar, and S. Singla.

Foundations of Software Technology and Theoretical Computer Science**(FSTTCS 2020)**

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

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

- On Using Storage and Genset for Mitigating Power Grid Failures

S. Singla, M.Math Thesis, University of Waterloo, April 2013 (slides)

- On the Spum and the Integral Spum of Graphs

S. Singla, A. Tiwari, and A. Tripathi.

Manuscript

- The School Bus and the Orienteering problem

S. Singla.

Course Project Report, CO754, Univ. Waterloo, Winter 2012

- 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