Jayadev Acharya

Jayadev Acharya

Assistant Professor

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


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

  • Paper on learning and testing causal models accepted to NIPS 2018.

  • Paper on differentially private testing accepted to NIPS 2018 as a spotlight presentation.

  • I am teaching Discrete Probability and Randomized Algorithms in Fall 2018. Class website here.

  • Invited talk on Shannon Channel. Please find slides here, and video here. The video has a couple of short interruptions with dropped connection. Apologies!!
  • New paper Communication Efficient, Sample Optimal, Linear Time Locally Private Discrete Distribution Estimation posted on arXiv.
  • New paper INSPECTRE: Privately Estimating the Unseen posted on arXiv.
  • Presented a talk, "Hadamard Response: Local Private Distribution Estimation", ITA 2018. Please find the slides here.
  • I am on the Program Committee of IEEE International Symposium on Information Theory (ISIT'18). Please submit your awesome work here!!
  • Measuring Quantum Entropy accepted as a talk at Quantum Information Processing (QIP'18).
  • A Chasm Between Identity and Equivalence Testing with Conditional Queries to appear in Theory of Computing.
  • Best Paper Award, Honorable Mention at International Conference on Machine Learning (ICML), 2017 for this paper.    (Top 4 of 1676 submissions)

  • Paper on one-bit compressive sensing accepted at ISIT 2017.
  • NSF CISE Research Initiation Initiative (NSF-CRII) award, 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.
  • Students

  • Sourbh Bhadane (co-advised with Aaron Wagner)

  • Ziteng Sun

  • Huanyu Zhang
  • Teaching

    Fall 2018: Discrete Probability and Randomized Algorithms
    Spring 2018: Machine Learning and Pattern Recognition
    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
    • Estimating Entropy of Distributions in Constant Space
      with S. Bhadane, P. Indyk, and Z. Sun

    • Test without Trust: Optimal Locally Private Distribution Testing [arXiv]
      with C. Canonne, C. Freitag, and H. Tyagi

    • Distributed Simulation and Distributed Inference [arXiv]
      with C. Canonne, and H. Tyagi

    • Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication [arXiv] , [pdf]
      with Z. Sun, and H. Zhang

    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)
    • Learning and Testing Causal Models with Interventions [arXiv]
      with A. Bhattacharyya, C. Daskalakis, and S. Kandasamy
      Advances in Neural Information Processing Systems (NIPS 2018)

    • Differentially Private Testing of Identity and Closeness of Discrete Distributions [arXiv]
      with Z. Sun, and H. Zhang
      Advances in Neural Information Processing Systems (NIPS 2018)
      Spotlight presentation (Acceptance: 4%)

    • INSPECTRE: Privately Estimating the Unseen [arXiv]
      with G. Kamath, Z. Sun, and H. Zhang
      International Conference on Machine Learning (ICML 2018)

    • Profile Maximum Likelihood is Optimal for Estimating KL Divergence
      IEEE International Symposium on Information Theory (ISIT 2018)

    • Improved Bounds on Minimax Risk of Estimating Missing Mass
      with Y. Bao, Y. Kang and Z. Sun
      IEEE International Symposium on Information Theory (ISIT 2018)
      TPC Choice Session (Acceptance: 4.4%)

    • Measuring Quantum Entropy [arXiv]
      with I. Issa, N. V. Shende, and A. B. Wagner
      Quantum Information Processing (QIP 2017)
      Video of Ibrahim's talk at QIP is here

    • 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