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?
Previously, I studied computer science and mathematics at Columbia University, where I was fortunate to have been mentored by Alexandr Andoni and Xi Chen.
ResearchSelectedAllAI/MLSublinear AlgorithmsCombinatoricsSystems
Authors are ordered alphabetically by convention
Attention via Black-Box Vector Search
with Alexandr Andoni, Ashwin Padaki, Styopa Zharkov
In Submission
Fast Geometric Spanners via Approximate Nearest Neighbor Search
with Alexandr Andoni, Manuel Paez, Tian Zhang
In Submission
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams
with Ashwin Padaki, Erik Waingarten
Preprint
Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
with Nathan White
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
MC$^2$: Rigorous and Efficient Directed Greybox Fuzzing
with Abhishek Shah, Dongdong She, Samanway Sadhu, Peter Coffman, Suman Jana
ACM CCS 2022 Honorable Mention for Best Paper Award
On the Size and Complexity of Scrambles
with Seamus Connor, Steven DiSilvio, Sasha Kononova, Ralph Morrison
In Submission
with Nila Cibu, Kexin Ding, Steven DiSilvio, Sasha Kononova, Chan Lee, Ralph Morrison
In Submission
Chip-Firing Games on Banana Trees
with Marchelle Beougher, Nila Cibu, Kexin Ding, Steven DiSilvio, Kristin Heysse, Sasha Kononova, Chan Lee, Ralph Morrison
In Submission
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.