Krish Singal
Contact: ksingal@seas.upenn.edu
Recent NewsI am currently a PhD student in CS Theory Group at the University of Pennsylvania, where I am extremely grateful to be advised by Erik Waingarten and Sanjeev Khanna. Previously, I studied computer science and mathematics at Columbia University, where I was fortunate to have been mentored by Alexandr Andoni and Xi Chen.
Broadly, my research interests lie at the intersection of algorithm design and machine learning. Some questions I have thought about include
- Efficient computation for machine learning systems. Can we design fast algorithms to perform operations/mechanisms fundamental to modern AI/ML systems (e.g. attention, quantization, etc.)?
- Sublinear algorithms for problems in high-dimensional geometry. Can we design fast and/or space-efficient algorithms for fundamental problems in high-dimensional geometry?
I am currently a co-organizer of the Penn Theory Seminar. Please reach out if you're interested in giving a talk!
Research [All|AI/ML|Sublinear Algorithms|Combinatorics|Systems]
Authors are ordered alphabetically unless otherwise noted ($\star$)
Equal contribution is denoted by ($\ast$)
Attention via Black-Box Vector Search$^{\star}$
Styopa Zharkov$^{\ast}$, Krish Singal$^{\ast}$, Ashwin Padaki$^{\ast}$, Alexandr Andoni$^{\ast}$
In Submission
Fast Geometric Spanners via Approximate Nearest Neighbor Search
Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang
In Submission
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams
Ashwin Padaki, Krish Singal, Erik Waingarten
In Submission
Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms$^{\star}$
Nathan White$^{\ast}$, Krish Singal$^{\ast}$
NeurIPS 2026
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten
MC$^2$: Rigorous and Efficient Directed Greybox Fuzzing$^{\star}$
Abhishek Shah, Dongdong She, Samanway Sadhu, Krish Singal, Peter Coffman, Suman Jana
ACM CCS 2022 Honorable Mention for Best Paper Award
On the Size and Complexity of Scrambles
Seamus Connor, Steven DiSilvio, Sasha Kononova, Ralph Morrison, Krish Singal
In Submission
Nila Cibu, Kexin Ding, Steven DiSilvio, Sasha Kononova, Chan Lee, Ralph Morrison, Krish Singal
In Submission
Chip-Firing Games on Banana Trees
Marchelle Beougher, Nila Cibu, Kexin Ding, Steven DiSilvio, Kristin Heysse, Sasha Kononova, Chan Lee, Ralph Morrison, Krish Singal
In Submission
Teaching/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.