Jayadev Acharya

Jayadev Acharya

Assistant Professor

Cornell University
email: acharya at cornell.edu


About Me

I am an assistant professor in Electrical and Computer Engineering, and a field member in Computer Science 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.

Openings

We are looking for prospective Ph.D students who are interested in developing algorithms and understanding fundamental limits for problems in data science, broadly defined.

News

  • 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

    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
    • A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation [pdf]
      with H. Das, A. Orlitsky, and A. T. Suresh
      Manuscript 2016

    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) (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)
    • Improved Bounds for Universal One-Bit Compressive Sensing [arXiv]
      with A. Bhattacharyya, and P. Kamath

    • 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