**Notice**

The paper versions given here are the most current, arxiv and other sources notwithstanding.

Errata may be found in the follow-up notes (when these are posted).

Please observe all copyright laws.

- A. Kontorovich, M. Raginsky. Concentration of measure without independence: a unified approach via the martingale method, Invited to The IMA volumes in mathematics and its applications, 2016.
- L. Gottlieb, A. Kontorovich, R. Krauthgamer. Adaptive Metric Dimensionality Reduction. Invited to
*Theoretical Computer Science*, 105-118, 2016. Extended abstract appeared in ALT 2013. - A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier, AISTATS 2015.
- L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors, NIPS 2014.
- D. Berend, A. Kontorovich. A finite sample analysis of the Naive Bayes classifier, JMLR 16, 1519-1545, 2015. A preliminary version, titled "Consistency of weighted majority votes" appeared in NIPS 2014.
- A. Kontorovich, Roi Weiss. Maximum Margin Multiclass Nearest Neighbors, ICML 2014.
- A. Kontorovich. Concentration in unbounded metric spaces and algorithmic stability, ICML 2014. follow-up notes
- 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. follow-up notes - 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"] - A. Kontorovich, A. Trachtenberg. Deciding unique decodability of bigram counts via finite automata.
*Journal of Computer and System Sciences*80(2), 450–456, 2014. - D. Angluin, J. Aspnes, S. Eisenstat, A. Kontorovich. On the Learnability of Shuffle Ideals.
*Journal of Machine Learning Research*14, 1513−1531, 2013. - D. Berend, A. Kontorovich. A Sharp Estimate of the Binomial Mean Absolute Deviation with Applications.
*Statistics and Probability Letters*83(4), 1254-1259, 2013. - D. Berend, A. Kontorovich. On the Concentration of the Missing Mass.
*Electronic Communications in Probability*18(3), 1-7, 2013. - A. Kontorovich. Obtaining Measure Concentration from Markov Contraction.
*Markov Processes and Related Fields*18, 613–638, 2012. - A. Kontorovich. Statistical estimation with bounded memory.
*Statistics and Computing*22(5), 1155-1164, 2012. [follow-up notes] - A. Kontorovich, B. Nadler. Universal Kernel-Based Learning with Applications to Regular Languages.
*Journal of Machine Learning Research*10, 997-1031, 2009. - A. Kontorovich, C. Cortes, M. Mohri. Kernel Methods for Learning Languages. Invited to
*Theoretical Computer Science*405, 223-236, 2008. [follow-up notes] - A. Kontorovich, K. Ramanan. Concentration Inequalities for Dependent Random Variables via the Martingale Method.
*Annals of Probability*36(6), 2126-2158, 2008. - A. Kontorovich. Uniquely Decodable
*n*-gram Embeddings.*Theoretical Computer Science*329, 271-284, 2004. - C. R. Shalizi, A. Kontorovich. Predictive PAC Learning and Process Decompositions. In NIPS 2013.
- A. Kontorovich, B. Nadler, R. Weiss. On learning parametric-output HMMs. In ICML 2013.
- L. Gottlieb, A. Kontorovich, R. Krauthgamer.
Efficient classification for metric data.
*IEEE Transactions on Information Theory*60(9), 5750-5759, 2014. [Conference version: COLT 2010.] - C. Cortes, A. Kontorovich, M. Mohri. Learning Languages with Rational Kernels. In COLT 2007.