Krish Singal
Contact: ksingal@seas.upenn.edu
Recent NewsI am a PhD student in the CS Theory Group at the University of Pennsylvania, where I am extremely grateful to be advised by Erik Waingarten and Sanjeev Khanna. My research interests lie in designing algorithms to make modern machine learning systems more efficient and effective. My work has been guided by the following questions
- Efficient computation for machine learning systems. Can we design fast and space-efficient algorithms to perform tasks fundamental to modern AI/ML systems, such as attention, quantization, clustering, and graph sparsification?
- Self-improving machine learning systems. How can we enable modern agentic systems to continually learn from their experience and improve over time?
I am spending Fall 2026 interning as an Applied Scientist at AWS, hosted by Nina Mishra and Tal Wagner. Previously, I studied computer science and mathematics at Columbia University, where I was fortunate to have been mentored by Alexandr Andoni and Xi Chen. During undergrad, I spent two summers interning as a software engineer at Apple and AWS.
ResearchSelectedAll
Authors are ordered alphabetically by convention
Fast Geometric Spanners via Approximate Nearest Neighbor SearchPreprint
with Alexandr Andoni, Manuel Paez, Tian Zhang
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic StreamsPreprint
with Ashwin Padaki, Erik Waingarten
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic StreamsFOCS 2025
with Sanjeev Khanna, Ashwin Padaki, Erik Waingarten short slideslong slidesvideo
MC$^2$: Rigorous and Efficient Directed Greybox FuzzingACM CCS 2022
with Abhishek Shah, Dongdong She, Samanway Sadhu, Peter Coffman, Suman Jana
Honorable Mention for Best Paper Award
On the Size and Complexity of ScramblesPreprint
with Seamus Connor, Steven DiSilvio, Sasha Kononova, Ralph Morrison
The Gonality of Chess GraphsPreprint
with Nila Cibu, Kexin Ding, Steven DiSilvio, Sasha Kononova, Chan Lee, Ralph Morrison
Chip-Firing Games on Banana TreesPreprint
with Marchelle Beougher, Nila Cibu, Kexin Ding, Steven DiSilvio, Kristin Heysse, Sasha Kononova, Chan Lee, Ralph Morrison
Selected Talks
Teaching and Service
I have served as a teaching assistant for the following course offerings
- Algorithms for Big Data taught by Anindya De and Erik Waingarten (Summer 2026, Spring 2026, Fall 2025), University of Pennsylvania
- Advanced Algorithms taught by Alexandr Andoni (Spring 2024), Columbia University
- Computational Complexity taught by Henry Yuen (Fall 2023), Columbia University
- Analysis of Algorithms taught by Christos Papadimitriou (Spring 2023, Fall 2022), Columbia University
In Fall 2023, I co-led a seminar on the Analysis of Boolean Functions as part of the Columbia Undergraduate Learning Seminar in Theoretical Computer Science. I co-wrote a partial solution manual for exercises in Ryan O'Donnell's Analysis of Boolean Functions.
I have served as a sub-reviewer for ITCS 2027, STACS 2026.
Miscellaneous
In my free time, I enjoy long-distance running, reading, writing, playing music, and watching movies.