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

I am a second 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 streaming and sketching algorithms for problems in big-data. In general, I like to think about problems regarding dimensionality reduction -- i.e. to what extent can we extract and compress the significant bits of some enourmous, noisy data-set.
Additionally, I am interested in communication complexity, machine learning, and optimization.

- 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 [pdf]

With Marcelo Arenas, Luis Alberto Croquevielle, and Cristian Riveros,**PODS 2019**

**PODS Best Paper Award, 2019**

- 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]

- Learning Stochastically Evolving Networks via Local Probing

Rajesh Jayaram, advised by Eli Upfal (Senior Thesis)

[pdf] [Defense Slides]

In the fall of 2016, I was the Head TA for CS157 – Design and Analysis of Algorithms, taught by Prof. Paul Valiant.

In the spring of 2016, I was a TA for CS22 – Discrete Structures and Probability .