Nathaniel Grammel

Email: <first initial><last name> AT umd DOT edu

Hello! I am a PhD student at the University of Maryland, College Park, advised by Aravind Srinivasan. Prior to this, I earned my Bachelors and Masters degrees in Computer Science at New York University’s Tandon School of Engineering, where my Masters thesis and research was advised by Lisa Hellerstein.

I am broadly interested in theoretical computer science, particularly in the design and analysis of algorithms for a wide variety of combinatorial problems motivated by real-world applications in artificial intelligence and machine learning. My research has focused on algorithms for optimization problems in stochastic settings and with uncertain or changing inputs (e.g., online algorithms). More recently, I have been interested in socially responsible ML and I am working on research in algorithmic fairness. More broadly, I am also interested in learning theory, deep learning, LLMs and foundations models, and other areas of machine learning which have seen significant developments recently.

I am on the job market in 2024. My CV is available upon request (by email).


[NB: In theoretical computer science papers, authors are typically listed in alphabetical order]

Drafts, Preprints, and Papers Under Review

Simultaneous Individual and Group Fairness in Covering Problems, under review at ICML.

Randomized Algorithms for Proportionally Fair Matching, under review at ICML.

Published Papers

Online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience, with B. Brubach, W. Ma, A. Srinivasan. Operations Research (2022).

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs, with C. MacRury and W. Ma. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023.

Algorithms for the Unit-Cost Stochastic Score Classification Problem, with L. Hellerstein, D. Kletenik, and N. Liu. Algorithmica 84 (2022).

The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions, with D. Gkenosis, L. Hellerstein, and D. Kletenik. Discrete Applied Mathematics 309 (2022).

Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes, with B. Brubach, W. Ma, A. Srinivasan. Neural Information Processing Systems (NeurIPS) 2021.

PettingZoo: A Standard API for Multi-Agent Reinforcement Learning, with J. K. Terry, and 11 other authors. Neural Information Processing Systems (NeurIPS) 2021.

Approximating Two-Stage Stochastic Supplier Problems, with B. Brubach, D. Harris, A. Srinivasan, L. Tsepenekas, A. Vullikanti. APPROX/RANDOM 2021.

Follow Your Star: New Frameworks for Online Stochastic Matching with Known and Unknown Patience, with B. Brubach, W. Ma, A. Srinivasan. AISTATS 2021.

The Stochastic Score Classification Problem, with D. Gkenosis, L. Hellerstein, D. Kletenik. European Symposium on Algorithms (ESA) 2018.

Universality in perfect state transfer, with E. Connelly, M. Kraut, L. Serazo, C. Tamon. Linear Algebra and Its Applications, Volume 531, 2017.

Scenario Submodular Cover, with L. Hellerstein, D. Kletenik, P. Lin. Approximation and Online Algorithms (WAOA) 2016.


I have worked as a teaching assistant for computer science courses at both UMD and NYU. In addition, I have taught courses and summer programs, and worked as a tutor. Some things I have taught:

  • CMSC 451, Summer 2023 at UMD. This is the advanced algorithms course geared towards undergraduate (primarily senior-level) computer science students.
  • CS-UY 1134, Summer 2019 at NYU Tandon. This is the introductory data structures and algorithms course, a required course for undergraduate computer science majors at NYU Tandon.
  • CS4CS and Cyber Girls, part of the Center for K-12 STEM Education at NYU. CS4CS is a summer program to teach computer science and cyber security to high school students. Cyber Girls was a program aimed at equipping high school teachers with knowledge and tools in cyber security and help them to be able to launch programs at their schools aimed at teaching cyber security and computer science fundamentals to high school girls in a fun and engaging way.