Research Interests

I am broadly interested in information theory, machine learning and statistics. Particular emphasis is on designing efficient algorithms for statistical and learning tasks, with the goal of optimality in all possible resources.

Publications

Manuscripts

Estimating Symmetric Properties of Distributions: A Maximum Likelihood Approach
with H. Das, A. Orlitsky, and A. T. Suresh
Manuscript 2015

Optimal Testing for Families of Distributions [arXiv] [pdf]
with C. Daskalakis, and G. Kamath
Manuscript 2015

Sample Optimal Density Estimation in Nearly-Linear Time [arXiv] [pdf]
with I. Diakonikolas, J. Li, L. Schmidt
Manusctupt 2015

Journals

String Reconstruction from Substring Compositions [pdf]
with H. Das, O. Milenkovic, A. Orlitsky, S. Pan
SIAM Journal on Discrete Mathematics, 29(3): 1340-1371, 2015

Preliminary versions: IEEE International Symposium on Information Theory (ISIT [2010, 2014])
Jack Keil Wolf Student Paper Award at ISIT 2010

Estimating Renyi Entropy of Discrete Distributions [arXiv] [video of Himanshu's talk at Simons]
with A. Orlitksy, A. T. Suresh, and H. Tyagi
IEEE Transactions on Information Theory (submitted)

Preliminary version: ACM-SIAM Symposium on Discrete Algorithms [SODA 2015] (Acceptance: 27%)

Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling [arXiv] [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
IEEE Transactions on Information Theory (in revision)

Preliminary version: IEEE International Symposium on Information Theory [ISIT 2014]

A Chasm Between Identity and Equivalence Testing with Conditional Queries [arXiv] [pdf]
with C. Canonne, and G. Kamath
Journal of Machine Learning Research (JMLR) (submitted)

Preliminary version: Randomization and Computation (RANDOM 2015) (Acceptance: 37.9%)

On the Computation and Verification Query Complexity of Symmetric Functions [pdf]
with H. Das, A. Jafarpour, A. Orlitsky and A. T. Suresh
IEEE Transactions on Information Theory (submitted)

Preliminary version: Allerton Conference on Communications and Controls [Allerton 2011]

Multilevel Thresholding for Image Segmentation through a Fast Statistical Recursive Algorithm [pdf]
with S. Arora, A. Verma, and P. K. Panigrahi
Pattern Recognition Letters 29(2): 119-125, 2008

Conferences (not mentioned above)

Adaptive Estimation in Weighted Group Testing [pdf]
with C. Canonne, and G. Kamath
IEEE International Symposium on Information Theory (ISIT 2015)

Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms [pdf]
with I. Diakonikolas, C. Hegde, J. Li, L. Schmidt
ACM Symposium on Principles of Database Systems (PODS 2015) (Acceptance: 31.2%)

Testing Poisson Binomial Distributions [arXiv] [pdf] [video of my talk at Simons]
with C. Daskalakis
ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) (Acceptance: 27%)

Near-Optimal-Sample Estimators For Spherical Gaussian Mixtures [arXiv] [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
Neural Information Processing Systems (NIPS 2014) (Acceptance: 24.7%)

Sublinear Algorithms for Outlier Detection and Generalized Closeness Testing [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
IEEE International Symposium on Information Theory (ISIT 2014)

Sorting with Adversarial Comparators and Application to Density Estimation [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
IEEE International Symposium on Information Theory (ISIT 2014)

Efficient Compression of Monotone and m-Modal Distributions [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
IEEE International Symposium on Information Theory (ISIT 2014)

A Competitive Test for Uniformity of Monotone Distributions [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
Artificial Intelligence and Statistics (AISTATS 2013) (Acceptance: 33.6%)

Optimal Probability Estimation with Applications to Prediction and Classification [pdf]
with A. Jafarpour, A. Orlitsky, and A. T. Suresh
Conference on Learning Theory (COLT 2013)

Tight Bounds for Universal Compression of Large Alphabets [pdf]
with H. Das, A. Jafarpour, A. Orlitsky, and A. T. Suresh
IEEE International Symposium on Information Theory (ISIT 2013)

Tight Bounds on Profile Redundancy and Distinguishability [pdf]
with H. Das, and A. Orlitsky
Advances in Neural Information Processing Systems (NIPS 2012) (Acceptance: 25.2%)

Competitive Classification and Closeness Testing [pdf]
with H. Das, A. Jafarpour, A. Orlitsky, S. Pan, and A. T. Suresh
Conference on Learning Theory (COLT 2012) (Acceptance: 30.2%)

Estimating Multiple Concurrent Processes [pdf]
with H. Das, A. Jafarpour, A. Orlitsky, and S. Pan
IEEE International Symposium on Information Theory (ISIT 2012)

Algebraic Computation of Pattern Maximum Likelihood [pdf]
with H. Das, A. Orlitsky, and S. Pan
IEEE International Symposium on Information Theory (ISIT 2011)

Competitive Closeness Testing [pdf]
with H. Das, A. Jafarpour, A. Orlitsky, and S. Pan
Conference on Learning Theory (COLT 2011) (Acceptance: 30.7%)

Classification Using Pattern Probability Estimators [pdf]
with H. Das, A. Orlitsky, S. Pan, and N. P. Santhanam
IEEE International Symposium on Information Theory (ISIT 2010)

Exact Calculation of Pattern Probabilities [pdf]
with H. Das, H. Mohimani, A. Orlitsky, and S. Pan
IEEE International Symposium on Information Theory (ISIT 2010)

Recent Results on Pattern Maximum Likelihood [pdf]
with A. Orlitsky, and S. Pan
IEEE Information Theory Workshop (ITW 2009)

The Maximum Likelihood Probability of Unique-Singleton, Ternary, and Length-7 Patterns [pdf]
with A. Orlitsky, and S. Pan
IEEE International Symposium on Information Theory (ISIT 2009)

Hierarchical zonation technique to extract common boundaries of a layered earth model [pdf]
with S. Goparaju, J. C. Goswami, and D. Heliot
IEEE Antenna and Propagation Symposium (AP-S 2007)