AI summary · arXiv: 1907.05056v1 · cs.GL
Kolmogorov complexity in the USSR (1975--1982): isolation and its end
The essentials
- The article discusses the "dark ages" of algorithmic information theory in the USSR from 1975 to 1982.
- Political and social factors led to a significant decrease in the number of people working in this area during this time.
- L.A. Levin published several seminal papers that laid the foundation for modern algorithmic information theory during this period.
- A.N. Kolmogorov's talk at a seminar sparked a new wave of interest among younger researchers who obtained new results in algorithmic information theory.
- Isolation from international research communities affected progress in this field, with political factors such as censorship and limited access to international literature impeding scientific research.
- Despite these challenges, researchers persisted with their work and made significant contributions to advancing our understanding of fundamental concepts related to computation and information processing.
- Collaborations with international researchers helped break down barriers and advance research in this field even further.
Key points written by AI: they may contain errors, check them against the paper.
Ask questions about this paper to our AI assistant
How to chat with this paper? Illustrated guide
You can also chat with multiple papers at once here.
Keep this conversation — a free account saves your questions and answers, your collections of papers and your alerts.
Continue with Google Create a free accountTools for this paper
Advanced tools Premium
For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium
Among the 26 papers around this one, the name that comes back most: N. Vereshchagin (4 papers)
10 more people sign several of them. The full map adds their institutions and approaches, from the papers of the last years.
Papers around this one
See them on a mapRanked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)A. Semenov, Alexander Shen, N. Vereshchagin · 2024 · Theory of Probability & Its Applications · cited 5 times · Not summarized yet
Abstract
The last theme of Kolmogorov’s mathematics research was algorithmic theory of information, now often called Kolmogorov complexity theory. Kolmogorov played a crucial role in its creation, though he was not the first who suggested measuring the amount of information in a finite object using theory of algorithms, as the length of the minimal description. Ray Solomonoff did this several years earlier, in the beginning of 1960s. [1, 3, 4]. However, Solomonoff’s work remained almost unnoticed before Kolmogorov’s publications (the first was in 1965) where he referred to Solomonoff’s work. Probably this happened not only because of Kolmogorov’s fame but also because Kolmogorov papers were well writ…
-
Kolmogorov Last Discovery? (Kolmogorov and Algorithmic Statictics)A. Semenov, A. Shen, N. Vereshchagin · 2023 · Not summarized yet
Abstract
The last theme of Kolmogorov's mathematics research was algorithmic theory of information, now often called Kolmogorov complexity theory. There are only two main publications of Kolmogorov (1965 and 1968-1969) on this topic. So Kolmogorov's ideas that did not appear as proven (and published) theorems can be reconstructed only partially based on work of his students and collaborators, short abstracts of his talks and the recollections of people who were present at these talks. In this survey we try to reconstruct the development of Kolmogorov's ideas related to algorithmic statistics (resource-bounded complexity, structure function and stochastic objects).
-
Around Kolmogorov complexity: basic notions and resultsA. Shen · 2015 · arXiv.org · preprint, not peer reviewed · cited 27 times · Not summarized yet
Abstract
Algorithmic information theory studies description complexity and randomness and is now a well-known field of theoretical computer science and mathematical logic. There are several textbooks and monographs devoted to this theory (Calude, Information and Randomness. An Algorithmic Perspective, 2002, Downey and Hirschfeldt, Algorithmic Randomness and Complexity, 2010, Li and Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2008, Nies, Computability and Randomness, 2009, Vereshchagin et al., Kolmogorov Complexity and Algorithmic Randomness, in Russian, 2013) where one can find a detailed exposition of many difficult results as well as historical references. However, it se…
-
KOLMOGOROV'S CONTRIBUTIONS TO INFORMATION THEORY AND ALGORITHMIC COMPLEXITYT. Cover, P. Gács, R. Gray · 1989 · Annals of Probability · cited 104 times · Not summarized yet
-
Kolmogorov's legacy: Algorithmic Theory of Informatics and Kolmogorov Programmable TechnologySergei Levashkin, V. Alexandrov, A. Guzmán-Arenas · 2020 · arXiv.org · preprint, not peer reviewed · Not summarized yet
Abstract
In this survey, we explore Andrei Nikolayevich Kolmogorov's seminal work in just one of his many facets: its influence Computer Science especially his viewpoint of what herein we call 'Algorithmic Theory of Informatics.' Can a computer file 'reduce' its 'size' if we add to it new symbols? Do equations of state like second Newton law in Physics exist in Computer Science? Can Leibniz' principle of identification by indistinguishability be formalized? In the computer, there are no coordinates, no distances, and no dimensions; most of traditional mathematical approaches do not work. The computer processes finite binary sequences i.e. the sequences of 0 and 1. A natural question arises: Should we…
-
Some theorems on the algorithmic approach to probability theory and information theory: (1971 Dissertation directed by A.N. Kolmogorov)L. Levin · 2010 · Annals of Pure and Applied Logic · cited 44 times · Not summarized yet
Abstract
This is a 1971 dissertation. Only its extended abstract was published at the time. While some results appeared in other publications, a number of details remained unpublished and may still have relevance.
-
Kolmogorov Complexity: Recent Research in MoscowV. Uspensky · 1996 · International Symposium on Mathematical Foundations of Computer Science · cited 1 time · Not summarized yet
-
Randomness Conservation Inequalities; Information and Independence in Mathematical TheoriesL. Levin · 1984 · Information and Control · cited 326 times · Not summarized yet
Abstract
The article further develops Kolmogorov's algorithmic complexity theory. The definition of randomness is modified to satisfy strong invariance properties (conservation inequalities). This allows definitions of concepts such as mutual information in individual infinite sequences. Applications to several areas, like probability theory, theory of algorithms, intuitionistic logic are considered. These theories are simplified substantially with the postulate that the objects they consider are independent of (have small mutual information with) any sequence specified by a mathematical property.
Prior work it builds on
-
Algorithmic Information TheoryG. Chaitin · 1977 · IBM Journal of Research and Development · cited 38 times · Not summarized yet
-
An Introduction to Kolmogorov Complexity and Its Applications, Third EditionMing Li, P. Vitányi · 1997 · Texts in Computer Science · cited 614 times · Not summarized yet
-
Combinatorial foundations of information theory and the calculus of probabilitiesA. Kolmogorov · 1983 · Russian Mathematical Surveys · cited 302 times · Not summarized yet
-
THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMSA. Zvonkin, L. Levin · 1970 · Russian Mathematical Surveys · cited 708 times · Not summarized yet
-
Kolmogorov's structure functions and model selectionN. Vereshchagin, P. Vitányi · 2002 · IEEE Transactions on Information Theory · cited 183 times · Not summarized yet
Abstract
In 1974, Kolmogorov proposed a nonprobabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The "structure function" of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. We show that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best fitting model in the class irrespective of whether the "true" model is in the model class c…
Papers that cite it
-
The universal measure of nonstochastic objectsVladimir Vovk · 2026 · cited 1 time · Not summarized yet
Abstract
The usual settings for discussing the notion of stochastic objects are very different from Kolmogorov's original structure-free setting, in which there is no predefined external structure on the objects (such as the lengths of binary strings). A natural modification of stochasticity, obtained by replacing finite sets as models with probability measures, is quasi-stochasticity. The structure-free setting is common in studies of quasi-stochasticity, and known results show that the universal machine generates non-quasi-stochastic objects with exponentially small probability. This paper shows that, on the other hand, the universal machine generates nonstochastic objects surprisingly often. It al…
-
Vladimir V'yugin: Short biography and some research contributionsP. Gács, Yuri Kalnishkan, Alexander Shen et al. · 2026 · Information and Computation · Not summarized yet
-
Testing exchangeability in the batch mode with e-values and Markov alternativesVladimir Vovk · 2023 · Machine-mediated learning · cited 4 times · Not summarized yet
Abstract
The topic of this paper is testing the assumption of exchangeability, which is the standard assumption in mainstream machine learning. The common approaches are online testing by betting (such as conformal testing) and the older batch testing using p-values (as in classical hypothesis testing). The approach of this paper is intermediate in that we are interested in batch testing by betting; as a result, p-values are replaced by e-values. As a first step in this direction, this paper concentrates on the Markov model as alternative. The null hypothesis of exchangeability is formalized as a Kolmogorov-type compression model, and the Bayes mixture of the Markov model w.r. to the uniform prior is…
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 6 November 2026.
The previous summary was created more than a year ago and can be re-run (if necessary) by clicking on the Run button below.
Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.