8 citations · 21 across the 5 of their papers we have counts for
5 papers
Random DFAs are Efficiently PAC Learnable
Leonid Aryeh Kontorovich
This paper has been withdrawn due to an error found by Dana Angluin and Lev Reyzin.
A Linear Programming Inequality with Applications to Concentration of Measure
Leonid Kontorovich
We prove an elementary yet useful inequality bounding the maximal value of certain linear programs. This leads directly to a bound on the martingale difference for arbitrarily depe…
Metric and Mixing Sufficient Conditions for Concentration of Measure
Leonid Kontorovich
We derive sufficient conditions for a family of metric probability spaces to have the measure concentration property. Specifically, if the sequence of pro…
Measure Concentration of Markov Tree Processes
Leonid Kontorovich
We prove an apparently novel concentration of measure result for Markov tree processes. The bound we derive reduces to the known bounds for Markov processes when the tree is a chai…
Measure Concentration of Hidden Markov Processes
Leonid Kontorovich
We prove what appears to be the first concentration of measure result for hidden Markov processes. Our bound is stated in terms of the contraction coefficients of the underlying Ma…