• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Some Properties of Antistochastic Strings
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
October 14, 2026
At HSE University–St Petersburg, Experts Discuss How AI Changes Tourist Routes and Cultural Heritage
Neural networks are no longer simple travel assistants; now they decide what to include on the route and what to skip. Artificial intelligence changes how people perceive a place and shapes the image of tourist centres. At the II International Scientific and Practical Conference ’Information Technologies in the Preservation and Promotion of Cultural Heritage,’ researchers discussed who controls algorithmic solutions and in what ways, and whether authentic traditions get lost in them.
October 12, 2026
Road Injuries Leading Cause of Death Among Men Aged 10 to 39
Worldwide, road injuries are the leading cause of death among males aged 10–39. An international team of researchers reached this conclusion as part of the Global Burden of Disease Study 2023, analysing data from 204 countries between 1990 and 2023. Their findings have been published in The Lancet Public Health, with HSE University Professor Vasily Vlassov listed among the collaborators.
October 8, 2026
HSE Experts Take Part in 23rd Annual Meeting of Valdai Discussion Club
The 23rd Annual Meeting of the Valdai Discussion Club was held from September 28 to October 1, 2026 under the theme ‘Responsibility for the Future: Limits of the Possible, or Limitless Possibilities?’ The forum brought together 120 experts from 40 countries, including representatives of China, the United States, India, Brazil, the United Kingdom, Germany, Egypt, Iran, and Japan.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Some Properties of Antistochastic Strings

P. 339–349.
Milovanov A.
In press

Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string x is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of x. Further we will show how it can be used for list decoding from erasing and prove that Symmetry of Information fails for total conditional complexity.

Language: English
DOI
Text on another site
Keywords: колмогоровская сложностьKolmogorov complexityалгоритмическая статистикаalgorithmic statisticstotal conditional complexitysymmetry of informationstochastic objectsстохастические объектытотальная условная сложностьсимметрия информации

In book

Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015
Vol. 9139. , Springer, 2015.
Similar publications
Space-Bounded Online Kolmogorov Complexity is Additive
Bruno Bauwens, Marchenko M., , in: 21st Conference on Computability in Europe, CiE 2025, Lisbon, Portugal, July 14–18, 2025, Proceedings. Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. (LNCS, volume 15764).: Cham: Springer, 2025. P. 133–142.
Abstract. The even online Kolmogorov complexity of a string x = x1x2 · · · xn is the minimal length of a program that for all i ≤ n/2, on input x1x3 · · · x2i−1 outputs x2i. The odd complexity is defined similarly. The sum of the odd and even complexities is called the dialogue complexity. In ...
Added: December 17, 2025
О базовых математических определениях цифровых технологий и искусственного интеллекта
Semenov A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 527 № S С. 7–12
The paper proposes a system of definitions for the basic concepts of computability theory that underlie the mathematics of the digital world: algorithm, computability, calculus, object complexity, close to modern undertnding. Hierarchies of the finite and the problem of consistency are considered. ...
Added: December 6, 2025
Kolmogorov’s Last Discovery? (Kolmogorov and Algorithmic Statistics)
Semenov A., Shen A., Vereshchagin N., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606
The definition of descriptional complexity of finite objects suggested by Kolmogorov and other authors in the mid-1960s is now well known. In addition, Kolmogorov pointed out some approaches to a more fine-grained classification of finite objects, such as the resource-bounded complexity (1965), structure function (1974), and the notion of $(\alpha,\beta)$-stochasticity (1981). Later it turned out ...
Added: January 16, 2025
On information content in certain objects
Vereshchagin N., / Series arXiv "math". 2024.
The fine approach to measure information dependence is based on the total conditional complexity CT(y|x), which is defined as the minimal length of a total program that outputs y on the input x. It is known that the total conditional complexity can be much larger than than the plain conditional complexity. Such strings x, y ...
Added: August 19, 2024
Последнее открытие Колмогорова? (Колмогоров и алгоритмическая статистика)
Vereshchagin N., Semenov A., Shen A., Теория вероятностей и ее применения 2023 Т. 68 № 4 С. 719–750
Помимо определения сложности описания конечных объектов (ныне называемой колмогоровской сложностью), Колмогоров наметил несколько способов более детального анализа свойств конечных объектов: сложность с ограничением на ресурсы (1965), структурную функцию (1974), а также понятие (α,β)-стохастичности (1981). Впоследствии выяснилось, что эти понятия по существу эквивалентны (дают одну и ту же кривую в разных координатах). В этом обзоре мы пытаемся ...
Added: October 25, 2023
Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time
Bauwens B. F., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9
In a lossless compression system with target lengths, a compressor 𝒞 maps an integer m and a binary string x to an m-bit code p, and if m is sufficiently large, a decompressor 𝒟 reconstructs x from p. We call a pair (m,x) achievable for (𝒞,𝒟) if this reconstruction is successful. We introduce the notion ...
Added: March 22, 2023
Inequalities for space-bounded Kolmogorov complexity
Bauwens B. F., Gács P., Romashchenko A. et al., Computability 2022 Vol. 11 No. 3-4 P. 165–185
Finding all linear inequalities for entropies remains an important open question in information theory. For a long time the only known inequalities for entropies of tuples of random variables were Shannon (submodularity) inequalities. Only in 1998 Zhang and Yeung 1998 found the first inequality that cannot be represented as a convex combination of Shannon inequalities, and ...
Added: December 23, 2022
Information disclosure in the framework of kolmogorov complexity
Vereshchagin N., Theoretical Computer Science 2023 Vol. 940 P. 108–122
We consider the network consisting of three nodes 1, 2, 3 connected by two open channels 1 → 2 and 1 → 3. The information present in the node 1 consists of four strings x , y , z , w. The nodes 2, 3 know x , w and need to know y , z, respectively. ...
Added: December 19, 2022
Predictions and Algorithmic Statistics for Infinite Sequences
Milovanov A., , in: Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings.: Springer, 2021. Ch. 17 P. 283–295.
We combine Solomonoff’s approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best “explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) ...
Added: August 11, 2021
The normalized algorithmic information distance can not be approximated
Bauwens B. F., Blinnikov I., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 130–141.
It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that ...
Added: February 5, 2021
Information Distance Revisited
Bauwens B. F., , in: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1–46:14.
Added: March 20, 2020
Descriptive complexity of computable sequences revisited
Vereshchagin N., Theoretical Computer Science 2020 Vol. 809 P. 531–537
The purpose of this paper is   to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58].   Namely, we consider   the following two   complexities of an infinite computable 0-1-sequence $\alpha$:   $C^{0'}(\alpha )$, defined as ...
Added: January 17, 2020
Методы математической статистики и алгоритмы обработки больших данных в инструменте объективного измерения уровня привлекательности розничной цены – «Ценометр» мобильного приложения «Покупайка»
Сметанин О. В., Ponomarenko A., В кн.: СБОРНИК ТЕЗИСОВ I научно-практической конференции «Демонстрация, практика внедрения и коммерциализация результатов интеллектуальной деятельности, полученных в рамках выполнения НИОКР. Преодоление технологических барьеров».: М.: ООО "Белый ветер", 2019.
«Покупайка» – это агрегатор цен розничной торговли, реализованный в виде мобильного приложения на платформах iOS и Android. Одной из главных функций системы является оценка привлекательности рыночных предложений для покупателя. Мы считаем предложение привлекательным (выгодным), если предлагаемая цена ниже, чем среднее значение по региону, с учетом текущего местоположения пользователя. В зависимости от разницы между заданным и среднестатистическим значением цены на товар, мы относим предложение к одной из нескольких ценовых ...
Added: October 28, 2019
Algorithmic Statistics: Forty Years Later.
Shen A., Vereshchagin N., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.
Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...
Added: October 26, 2018
Комбинаторные леммы для детерминированных контекстно-свободных языков
Rubtsov A. A., В кн.: Сборник научных трудов МФТИ "Модели и методы обработки информации".: Долгопрудный: МФТИ, 2016. С. 67–74.
В работе исследуются комбинаторные свойства детерминированных контекстно-свободных языков. Получена новая комбинаторная лемма, схожая по типу с леммами о накачке для КС-языков, а также получены комбинаторные свойства, следующие из модифицированной известной техники, опирающейся на Колмогоровскую сложность. ...
Added: October 20, 2018
On Algorithmic Statistics for Space-bounded Algorithms
Milovanov A., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833–848
Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we ...
Added: October 17, 2018
Plain stopping time and conditional complexities revisited
Posobin G. I., Shen A., Andreev M., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–24.
In this paper we analyze the notion of "stopping time complexity", informally defined as the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic (2016). It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) ...
Added: October 11, 2018
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit