110 citations · 131 across the 7 of their papers we have counts for
7 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.
Constructing processes with prescribed mixing coefficients
Leonid, Kontorovich
The rate at which dependencies between future and past observations decay in a random process may be quantified in terms of mixing coefficients. The latter in turn appear in strong…
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…