Madhav Jha

Currently, I am at Sigma Computing where we are changing the way business analysis is done by letting you use your data warehouse like a spreadsheet (think Google sheet or MS Excel). We are hiring so reach out if this sounds fun. Recently, I was an Applied Scientist at Amazon AI. I had Edo Liberty as my cool manager. Previously, I worked as a Software Developer at Zenefits . Prior to Zenefits, I was the John von Neumann Postdoctoral Research Fellow at Sandia National Labs in Livermore, California. At Sandia, I mainly worked with Sesh, Ali, and Tammy. Before starting the postdoc, I finished my PhD in Computer Science and Engineering from Pennsylvania State University under the guidance of Prof. Sofya Raskhodnikova. In 2008, I received an undergraduate degree (B.Tech) in Computer Engineering from Institute of Technology, Banaras Hindu University, India.

Research Interests
I primarily work on theoretical aspects of computer science, focusing on the design and analysis of sublinear algorithms. These algorithms are restricted to run in sublinear time (e.g. property testers) and/or sublinear space (e.g. streaming algorithms). In my thesis research, I studied the Lipschitz property of functions in the context of property testing and property reconstruction, and explored how these algorithms might find use in the area of data privacy (specifically, differential privacy). I have recently become interested in applications of sublinear algorithms in data mining, particularly, mining of massive graphs.

Conference Publications Links

Property Testing on Product Distributions:Optimal Testers for Bounded Derivative Properties arXiv
with Deeparnab Chakrabarty, Kashyap Dixit, and C. Seshadhri
The 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts arXiv
with C. Seshadhri and Ali Pinar
The 24th International Conference on World Wide Web, WWW 2015

Counting triangles in real-world graph streams: Dealing with repeated edges and time windows arXiv
with C. Seshadhri and Ali Pinar
The 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

A Space Efficient Streaming Algorithm for Triangle Counting using the Birthday Paradox arXiv
with C. Seshadhri and Ali Pinar
The 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2013 (Best student paper award)

Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy link
with Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova and Abhradeep Thakurta
The 10th Theory of Cryptography Conference (TCC) 2013

Limitations of Local Filters of Lipschitz and Monotone Functions PDF
with Pranjal Awasthi, Marco Molinaro and Sofya Raskhodnikova
The 16th International Workshop on Randomization and Computation (RANDOM) 2012

Testing Lipschitz Functions on Hypergrid Domains PDF
with Pranjal Awasthi, Marco Molinaro and Sofya Raskhodnikova
The 16th International Workshop on Randomization and Computation (RANDOM) 2012

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy PDF
with Sofya Raskhodnikova
The 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2011

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners link
with Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff
The 14th International Workshop on Randomization and Computation (RANDOM) 2010

Journal Publications

Testing Lipschitz Functions on Hypergrid Domains link
with Pranjal Awasthi, Marco Molinaro and Sofya Raskhodnikova
Algorithmica 2016

A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox link
with C. Seshadhri and Ali Pinar
ACM Transactions on Knowledge Discovery from Data, TKDD 2015

Limitations of Local Filters of Lipschitz and Monotone Functions link
with Pranjal Awasthi, Marco Molinaro, and Sofya Raskhodnikova
ACM Transactions on Computation Theory, TOCT 2014

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy PDF
with Sofya Raskhodnikova
SIAM Journal of Computing (SICOMP) 2013

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners PDF
with Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David P. Woodruff
SIAM Journal of Discrete Mathematics (SIDMA) 2012

Others

Property Testing and Reconstruction with Applications to Data Privacy
PhD Thesis (Defended May 2013)