• Publications

Preprints

• D. Berend, A. Kontorovich. The state complexity of random DFAs.
• A. Asor, A. Kontorovich. On the Additive Properties of the Fat-Shattering Dimension. [follow-up notes]
• A. Kontorovich, Roi Weiss. Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes.
• D. Berend, P. Harremoës, A. Kontorovich. A Reverse Pinsker Inequality.
• A. Kontorovich, A. Trachtenberg. Unique decodability of bigram counts by finite automata.

Journals

1. D. Angluin, J. Aspnes, S. Eisenstat, A. Kontorovich. On the Learnability of Shuffle Ideals. accepted to Journal of Machine Learning Research.
2. 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.
3. D. Berend, A. Kontorovich. A Sharp Estimate of the Binomial Mean Absolute Deviation with Applications. Statistics and Probability Letters 83(4), 1254-1259, 2013.
4. D. Berend, A. Kontorovich. On the Concentration of the Missing Mass. Electronic Communications in Probability 18(3), 1-7, 2013.
5. A. Kontorovich. An inequality involving the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. accepted to Analysis and Applications.
6. A. Kontorovich. An Explicit Bound on the Transportation Cost Distance. Communications in Mathematical Analysis 14(1), 1-14, 2013.
7. L. Chekina, D. Gutfreund, A. Kontorovich, L. Rokach, B. Shapira. Exploiting Label Dependencies for Improved Sample Complexity. Machine Learning 1-42, 2012.
8. A. Kontorovich, A. Brockwell. A Strong Law of Large Numbers for Strongly Mixing Processes. accepted to Communications in Statistics – Theory and Methods.
9. A. Kontorovich. Obtaining Measure Concentration from Markov Contraction. Markov Processes and Related Fields 18, 613–638, 2012.
10. D. Berend, A. Kontorovich. The Missing Mass Problem. Statistics and Probability Letters 82(6), 1102-1110, 2012.
11. L. Gottlieb, A. Kontorovich, E. Mossel. VC bounds on the cardinality of nearly orthogonal function classes. Discrete Mathematics 312(10), 1766-1775, 2012.
12. A. Kontorovich. Statistical estimation with bounded memory. Statistics and Computing 22(5), 1155-1164, 2012. [follow-up notes]
13. 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.
14. A. Kontorovich, B. Nadler. Universal Kernel-Based Learning with Applications to Regular Languages. Journal of Machine Learning Research 10, 997-1031, 2009.
15. A. Kontorovich, C. Cortes, M. Mohri. Kernel Methods for Learning Languages. Theoretical Computer Science 405, 223-236, 2008. [follow-up notes]
16. A. Kontorovich. Constructing processes with prescribed mixing coefficients. Statistics and Probability Letters 78, 2910-2915, 2008.
17. A. Kontorovich, K. Ramanan. Concentration Inequalities for Dependent Random Variables via the Martingale Method. Annals of Probability 36(6), 2126-2158, 2008.
18. A. Kontorovich. Uniquely Decodable n-gram Embeddings. Theoretical Computer Science 329, 271-284, 2004.
19. 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.

Conferences

1. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Adaptive Metric Dimensionality Reduction. to appear in ALT 2013.
2. A. Kontorovich, B. Nadler, R. Weiss. On learning parametric-output HMMs. In ICML 2013.
3. A. Filtser, J. Jin, A. Kontorovich, A. Trachtenberg. Efficient determination of the unique decodability of a string. to appear in ISIT 2013.
4. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. to appear in SIMBAD 2013.
5. D. Angluin, J. Aspnes, A. Kontorovich. On the Learnability of Shuffle Ideals. In ALT 2012.
6. A. Kontorovich, A. Trachtenberg. String reconciliation with unknown edit distance. In ISIT 2012.
7. A. Kontorovich, D. Hendler, E. Menahem. Metric Anomaly Detection Via Asymmetric Risk Minimization. In SIMBAD 2011.
8. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient classification for metric data. In COLT 2010.
9. D. Angluin, D. Eisenstat, A. Kontorovich, L. Reyzin. Lower Bounds on Learning Random Structures with Statistical Queries. In ALT 2010.
10. A. Kontorovich. A Universal Kernel for Learning Regular Languages. In MLG 2007 (distinguished contribution award). [watch video]
11. C. Cortes, A. Kontorovich, M. Mohri. Learning Languages with Rational Kernels. In COLT 2007.
12. A. Kontorovich, C. Cortes, M. Mohri. Learning Linearly Separable Languages. In ALT 2006. [follow-up notes]
13. 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.

Unrefereed

• A. Kontorovich. Measure Concentration of Strongly Mixing Processes with Applications, PhD thesis. [follow-up notes]
• A. Kontorovich. Metric and Mixing Sufficient Conditions for Concentration of Measure, manuscript.
• A. Kontorovich, J. Lafferty, D. Blei. Variational Inference and Learning for a Unified Model of Syntax, Semantics and Morphology, CMU technical report, 2006.
• A. Kontorovich, D. Ron, Y. Singer. A Markov Model for the Acquisition of Morphological Structure. CMU technical report, 2003.