Littlestone Dimension, Trees and Threshold Dimension

Learn about online learning problems and key complexity measures in this Russian-language tutorial from the historic Kolmogorov seminar series on computational complexity. Explore the Littlestone dimension concept, which represents the minimum number of errors across learning strategies against an adversary selecting functions from a given class. Examine how this dimension relates to tree structures and connects to the threshold dimension. Delve into foundational theoretical computer science concepts as presented at the seminar series established by the renowned mathematician Andrey Kolmogorov in 1979.