
Rajesh Jayaram
Email: rkjayara (at) cs (dot) cmu (dot) edu
Office: GHC 5105

I am a third year PhD student in theoretical computer science at Carnegie Mellon University, where I am fortunate to be advised by David Woodruff. I graduated with a B.Sc. from Brown University in May of 2017, where I concentrated in mathematics and computer science.
My research interests are primarily in randomized algorithms, specifically sketching and sampling algorithms for problems in bigdata. In general, I like to think about problems regarding dimensionality reduction  i.e. to what extent can we extract and compress the significant components of some enormous, noisy dataset.
Additionally, I am interested in machine learning, compressed sensing, and optimization.
Publications
 Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
With Huain Diao, Zhao Song, Wen Sun, and David Woodruff, NeurIPS 2019
Full Version on [arXiv]
 Towards Optimal Moment Estimation in Streaming and Distributed Models
With David Woodruff, APPROX 2019
Full Version on [arXiv]
 Learning Two Layer Rectified Neural Networks in Polynomial Time
With Ainesh Bakshi and David Woodruff, COLT 2019
Full Version on [arXiv]
 Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
With Marcelo Arenas, Luis Alberto Croquevielle, and Cristian Riveros, PODS 2019
PODS Best Paper Award, 2019
Full Version on [arXiv]
 Weighted Reservoir Sampling from Distributed Streams
With Gokarna Sharma, Srikanta Tirthapura, and David P. Woodruff, PODS 2019
Full Version on [arXiv]
 Perfect $L_p$ Sampling in a Data Stream
With David Woodruff, FOCS 2018
Full Version on [arXiv]
 Data Streams with Bounded Deletions
With David Woodruff, PODS 2018
Full Version on [arXiv]
 Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
With Barna Saha, ICALP 2017
Conference Version [pdf]
Miscellaneous:
Teaching
In the fall of 2019, I TA'd CS15859 – Algorithms for Big Data at CMU,
taught by David Woodruff.
In the spring of 2019, I TA'd CS15451/651 – Algorithms at CMU,
taught by David Woodruff and Anupam Gupta.
Teaching at Brown
In the fall of 2016, I was the Head TA for CS157 – Design and Analysis of Algorithms,
taught by Paul Valiant.
In the spring of 2016, I was a TA for CS22 – Discrete Structures and Probability .