Jayadev Acharya

Jayadev Acharya

Assistant Professor

Cornell University
382, Rhodes Hall
email: acharya at cornell.edu


About Me

I am an assistant professor in Electrical and Computer Engineering, and a graduate field member in Computer Science, and Operations Research and Information Engineering at Cornell University. I was a postdoctoral researcher in the Theory of Computation Group at MIT, hosted by Piotr Indyk. I obtained my PhD in Electrical and Computer Engineering from UC San Diego, where I was advised by Alon Orlitsky. Before that, I got a Bachelors degree in Electronics and Electrical Communication Engineering from IIT Kharagpur.

Research Interests

Algorithmic Statistics, Information Theory, and Machine Learning.

News

  • Nov'17 New paper Measuring Quantum Entropy posted on arXiv.
  • Nov'17 A Chasm Between Identity and Equivalence Testing with Conditional Queries to appear in Theory of Computing.
  • Oct'17 Invited talk "A Unified Estimator for (all?) Symmetric Distribution Properties'', at Allerton 2017.
  • Jul'17 Best Paper Award, Honorable Mention at International Conference on Machine Learning (ICML), 2017 for this paper.    (Top 4 of 1676 submissions)

  • I am teaching Algorithmic and Information Theoretic Methods in Data Science in Fall 2017. Class website here.

  • New paper on differentially private hypothesis testing posted on arXiv.
  • Paper on sample-optimality of maximum likelihood for distributions properties to be published at ICML 2017.
  • Paper on one-bit compressive sensing accepted at ISIT 2017.
  • NSF CISE Research Initiation Initiative (NSF-CRII) award, 2017.
  • Presented our work on proving sample-optimality of a unified approach for estimating distribution properties at ITA 2017. Please find the slides here.
  • I am teaching Machine Learning and Pattern Recognition in the Spring of 2017.
  • Alon Orlitsky, Ananda Suresh, and I presented a tutorial on information theoretic aspects of data science and machine learning at IEEE International Symposium on Informtion Theory (ISIT) 2016. The slides are here.
  • Teaching

    Fall 2017: Algorithmic and Information Theoretic Methods in Data Science
    Spring 2017: Machine Learning and Pattern Recognition
    Fall 2016: An Algorithmic and Information-Theoretic Toolbox for Massive Data

    Personal

    I am married to the beautiful Snigdha Mahapatra. We spend a good fraction of our time running after this.

    Publications

    MANUSCRIPTS
    • Differentially Private Testing of Identity and Closeness of Discrete Distributions [arXiv]
      with Z. Sun, and H. Zhang
      Manuscript 2017

    JOURNALS
    • String Reconstruction from Substring Compositions [pdf]
      with H. Das, O. Milenkovic, A. Orlitsky, and 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] [ pdf]
      with A. Orlitksy, A. T. Suresh, and H. Tyagi
      IEEE Transactions on Information Theory , 63(1): 38-56, 2017

      • 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
      Theory of Computing (ToC) (to appear)

      • 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)
    • A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation [pdf]
      with H. Das, A. Orlitsky, and A. T. Suresh
      International Conference on Machine Learning (ICML 2017)

    • Improved Bounds for Universal One-Bit Compressive Sensing [arXiv]
      with A. Bhattacharyya, and P. Kamath
      IEEE International Symposium on Information Theory (ISIT 2017)

    • Sample Optimal Density Estimation in Nearly-Linear Time [arXiv] [pdf]
      with I. Diakonikolas, J. Li, and L. Schmidt
      ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

    • Fast Algorithms for Segmented Regression [pdf]
      with I. Diakonikolas, J. Li, and L. Schmidt
      International Conference on Machine Learning (ICML 2016) (Acceptance: 24.3%)

    • Optimal Testing for Properties of Distributions [arXiv][pdf]
      with C. Daskalakis, and G. Kamath
      Advances in Neural Information Processing Systems (NIPS 2015) (Acceptance: 21.9%)
      Spotlight presentation (Acceptance: 4.5%)

    • 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, and L. Schmidt
      ACM Symposium on Principles of Database Systems (PODS 2015) (Acceptance: 31.2%)

    • Testing Poisson Binomial Distributions [arXiv] [pdf]
      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
      Advances in 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)

    THESIS
  • Estimation and Compression over Large Alphabets [pdf]
    PhD Thesis, University of California, San Diego, 2014