The paper versions given here are the most current, arxiv and other sources notwithstanding.
Please observe all copyright laws.



  1. D. Berend, A. Kontorovich. A finite sample analysis of the Naive Bayes classifier, accepted to JMLR.
  2. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient classification for metric data. IEEE Transactions on Information Theory 60(9), 5750-5759, 2014.
  3. A. Asor, H. Duan, A. Kontorovich. On the Additive Properties of the Fat-Shattering Dimension. IEEE Transactions on Neural Networks and Learning Systems 25(12), 2309-2312, 2014.
  4. A. Kontorovich, Roi Weiss. Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes. Journal of Applied Probability 51, 1-14, 2014.
  5. D. Berend, P. Harremoës, A. Kontorovich. Minimum KL-divergence on complements of $L_1$ balls. IEEE Transactions on Information Theory 60(6), 3172-3177, 2014. [Former title: "A Reverse Pinsker Inequality"]
  6. A. Kontorovich, A. Trachtenberg. Deciding unique decodability of bigram counts via finite automata. Journal of Computer and System Sciences 80(2), 450–456, 2014.
  7. D. Angluin, J. Aspnes, S. Eisenstat, A. Kontorovich. On the Learnability of Shuffle Ideals. Journal of Machine Learning Research 14, 1513−1531, 2013.
  8. T. Becker, A. Greaves-Tunnell, A. Kontorovich, S. J. Miller, K. Shen. Virus Dynamics on Starlike Graphs. Journal of Nonlinear Systems and Applications 4(1), 53-63, 2013.
  9. D. Berend, A. Kontorovich. A Sharp Estimate of the Binomial Mean Absolute Deviation with Applications. Statistics and Probability Letters 83(4), 1254-1259, 2013.
  10. D. Berend, A. Kontorovich. On the Concentration of the Missing Mass. Electronic Communications in Probability 18(3), 1-7, 2013.
  11. A. Kontorovich. An inequality involving the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. Analysis and Applications 11(6), 2013.
  12. A. Kontorovich. An Explicit Bound on the Transportation Cost Distance. Communications in Mathematical Analysis 14(1), 1-14, 2013.
  13. L. Chekina, D. Gutfreund, A. Kontorovich, L. Rokach, B. Shapira. Exploiting Label Dependencies for Improved Sample Complexity. Machine Learning 1-42, 2012.
  14. A. Kontorovich, A. Brockwell. A Strong Law of Large Numbers for Strongly Mixing Processes. accepted to Communications in Statistics – Theory and Methods.
  15. A. Kontorovich. Obtaining Measure Concentration from Markov Contraction. Markov Processes and Related Fields 18, 613–638, 2012.
  16. D. Berend, A. Kontorovich. The Missing Mass Problem. Statistics and Probability Letters 82(6), 1102-1110, 2012.
  17. L. Gottlieb, A. Kontorovich, E. Mossel. VC bounds on the cardinality of nearly orthogonal function classes. Discrete Mathematics 312(10), 1766-1775, 2012.
  18. A. Kontorovich. Statistical estimation with bounded memory. Statistics and Computing 22(5), 1155-1164, 2012. [follow-up notes]
  19. B. Nadler, A. Kontorovich. Model Selection for Sinusoids in Noise: Statistical Analysis and a New Penalty Term. IEEE Transactions on Signal Processing 59(4), 1333-1345, 2010.
  20. A. Kontorovich, B. Nadler. Universal Kernel-Based Learning with Applications to Regular Languages. Journal of Machine Learning Research 10, 997-1031, 2009.
  21. A. Kontorovich, C. Cortes, M. Mohri. Kernel Methods for Learning Languages. Invited to Theoretical Computer Science 405, 223-236, 2008. [follow-up notes]
  22. A. Kontorovich. Constructing processes with prescribed mixing coefficients. Statistics and Probability Letters 78, 2910-2915, 2008.
  23. A. Kontorovich, K. Ramanan. Concentration Inequalities for Dependent Random Variables via the Martingale Method. Annals of Probability 36(6), 2126-2158, 2008.
  24. A. Kontorovich. Uniquely Decodable n-gram Embeddings. Theoretical Computer Science 329, 271-284, 2004.
  25. H. Pratt, A. Polyakov, A. Kontorovich. Evidence for Separate Processing in the Human Brainstem of Interaural Intensity and Temporal Disparities for Sound Lateralization. Hearing Research 108, 1-8, 1997.


  1. L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors, NIPS 2014.
  2. D. Berend, A. Kontorovich. Consistency of weighted majority votes, NIPS 2014.
  3. A. Kontorovich, Roi Weiss. Maximum Margin Multiclass Nearest Neighbors, ICML 2014.
  4. A. Kontorovich. Concentration in unbounded metric spaces and algorithmic stability, ICML 2014.
  5. D. Gutfreund, A. Kontorovich, R. Levy, M. Rosen-Zvi. Boosting Conditional Probability Estimators. Invited to ISAIM Theory of Machine Learning Special Session, 2014.
  6. C. R. Shalizi, A. Kontorovich. Predictive PAC Learning and Process Decompositions. In NIPS 2013.
  7. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Adaptive Metric Dimensionality Reduction. In ALT 2013.
  8. A. Kontorovich, B. Nadler, R. Weiss. On learning parametric-output HMMs. In ICML 2013.
  9. A. Filtser, J. Jin, A. Kontorovich, A. Trachtenberg. Efficient determination of the unique decodability of a string. In ISIT 2013.
  10. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. In SIMBAD 2013.
  11. D. Angluin, J. Aspnes, A. Kontorovich. On the Learnability of Shuffle Ideals. In ALT 2012.
  12. A. Kontorovich, A. Trachtenberg. String reconciliation with unknown edit distance. In ISIT 2012.
  13. A. Kontorovich, D. Hendler, E. Menahem. Metric Anomaly Detection Via Asymmetric Risk Minimization. In SIMBAD 2011.
  14. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient classification for metric data. In COLT 2010.
  15. D. Angluin, D. Eisenstat, A. Kontorovich, L. Reyzin. Lower Bounds on Learning Random Structures with Statistical Queries. In ALT 2010.
  16. A. Kontorovich. A Universal Kernel for Learning Regular Languages. In MLG 2007 (distinguished contribution award). [watch video]
  17. C. Cortes, A. Kontorovich, M. Mohri. Learning Languages with Rational Kernels. In COLT 2007.
  18. A. Kontorovich, C. Cortes, M. Mohri. Learning Linearly Separable Languages. In ALT 2006. [follow-up notes]
  19. A. Kontorovich, D. Lee. Learning Semitic Vocalization with Hidden Markov Models. "Problems in Semitic NLP," NIPS Workshop on Machine Learning Methods for Text and Images 2001. Full tech report.