Aditya Krishnan

I am a fourth year Ph.D. student in Computer Science at Johns Hopkins University, advised by Vladimir Braverman. Previously I earned a B.S. (2013-2017) and M.S. (2017-2018) in Computer Science from Carnegie Mellon University where I was fortunate to work with Anupam Gupta, Kirk Pruhs, David P. Woodruff and Anil Ada.

Email  /  CV  /  Google Scholar  /  LinkedIn

profile photo

Broadly, I am interested in designing efficient algorithms with provable guarantees for problems in data science and machine learning. More specifically, I have worked on sketching and coreset methods for problems in randomized numerical linear algebra, optimization and machine learning.

b3do Projective Clustering Product Quantization
Aditya Krishnan, Edo Liberty
In Submission, 2021

Our method uses projective clustering which produces more quantization centers resulting in more accurate results for max dot-product search.

b3do Sublinear Time Spectral Density Estimation
Vladimir Braverman, Aditya Krishnan, Christopher Musco
In Submission, 2021

We present a method to estimate the spectral density of any Hermitian matrix using approximate matrix-vector multiplications.

b3do Lifelong Learning with Sketched Structural Regularization
Haoran Li, Aditya Krishnan, Jingfeng Wu, Soheil Kolouri, Praveen K. Pilly, Vladimir Braverman
Asian Conference in Machine Learning (ACML), 2021

We show sketching methods improve structural regularization algorithms for lifelong learning.

Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
Conference on Learning Theory (COLT), PMLR, 2021

We show a sampling method that sparsifies numerically sparse matrices and give error guarantees in the spectral norm.

Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff
International Conference on Machine Learning (ICML), 2020

We give an algorithm for estimating the Schatten p-norm of sparse matrices in row-order streams with space complexity that is dimension-independent.

Competitively Pricing Parking in a Tree
Max Bender, Jacob Gilbert, Aditya Krishnan, Kirk Pruhs
Conference on Web and Internet Economics (WINE), 2020

We give a poly-log competitive posted-price algorithm for online metrical searching .

On Sketching the q to p Norms
Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff
International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2018

We give sketching algorithms to approximate Schatten q to p norms, settling the linear sketch dimension for various values of q and p.


Teaching Assistant, 601.433/601.633 Introduction to Algorithms: F19, S20, S22
Teaching Assistant, 601.435/601.635 Approximation Algorithms: S21

Co-organizer, JHU CS Theory Seminar, F21, S22

Template: this