• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • Inequalities for space-bounded Kolmogorov complexity
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 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
  • еще
Тематика
Новости
13 октября 2026 г.
Российские ученые поставили под сомнение установление рекорда в замерах свойств сверхпроводников
Топологические изоляторы проводят ток только по поверхности и поэтому рассматриваются как перспективные материалы для будущей электроники и квантовых технологий. Особый интерес представляет их контакт со сверхпроводниками. Физики из НИУ ВШЭ показали, что недавний эксперимент, в котором в такой гибридной структуре якобы наблюдалось объединение электронных пар на рекордном расстоянии 1,5 мкм, допускает более прозаичное объяснение. По их мнению, тот же сигнал может быть обусловлен обычным прохождением электронов через сверхпроводник. Дискуссия исследователей развернулась на страницах Nature Physics.
12 октября 2026 г.
Устойчивое управление и стоимость бизнеса: экономисты ВШЭ выяснили, как они связаны на российском рынке
На российском рынке устойчивое развитие повышает стоимость бизнеса прежде всего тогда, когда становится частью корпоративной стратегии. К такому выводу пришли исследователи НИУ ВШЭ и их зарубежные коллеги, проанализировав практики управления 152 публичных российских компаний. Статья опубликована в журнале Business Strategy and the Environment.
8 октября 2026 г.
Ученые НИУ ВШЭ выяснили, что рейтинг врача более убедителен для пациентов, чем стаж
Исследователи НИУ ВШЭ изучили, как стаж и рейтинг врачей влияют на доверие пациентов к медицинской информации. Оказалось, что люди считают более убедительным мнение врачей, у которых высокий рейтинг, а на опыт работы обращают меньше внимания. Результаты опубликованы в журнале Frontiers in Human Neuroscience.

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

Inequalities for space-bounded Kolmogorov complexity

Computability. 2022. Vol. 11. No. 3-4. P. 165–185.
Баувенс Б. Ф., Gács P., Romashchenko A., Шень А.
Научное направление: Компьютерные науки Математика
Язык: английский
Полный текст
DOI
Текст на другом сайте
Ключевые слова: Kolmogorov complexityAlgorithmic information theorylinear inequalitiesspace bounds
Похожие публикации
РАЗРАБОТКА МЕТОДА И АЛГОРИТМОВ АДАПТИВНОГО ФЕДЕРАТИВНОГО ОБУЧЕНИЯ С УЧЕТОМ РАСПРЕДЕЛЕННОГО ЗАПАЗДЫВАНИЯ КЛИЕНТСКИХ ОБНОВЛЕНИЙ
Зыков С. В., Ермаков С. Р., Современные наукоемкие технологии 2026 № 9 С. 43–53
При федеративном обучении с неоднородными клиентскими данными и переменными задержками запоздавшие обновления могут ухудшать качество модели, а обмен параметрами с глобальным сервером увеличивает сетевую нагрузку. Целью исследования является разработка и теоретико-экспериментальное обоснование метода и алгоритмов адаптивного федеративного обучения с учетом распределенного запаздывания клиентских обновлений. Для обоснования разрабатываемых решений использованы событийная и непрерывная модели градиентных обновлений, ...
Добавлено: 11 октября 2026 г.
О воспроизводимости анализа временных рядов на основе матричных профилей
Брычков М. Е., Незнанов А.А., Программирование 2026 № 4 С. 50–66
Матричный профиль (МП) при появлении в 2016 г. быстро стал одним из важнейших методов предобработки, облегчающим решение широкого класса задач анализа временных рядов, в частности, задач обнаружения аномалий и шаблонов. Высокая значимость привела к появлению разнообразных инструментов вычисления МП, но оказалось, что особенности реализации методов существенно влияют на результаты, которые перестают быть идентичными. Встает вопрос, ...
Добавлено: 9 октября 2026 г.
Теория вероятностей и математическая статистика. Олимпиадные задачи.
ООО "Издательство Юрайт ", 2026.
Сборник олимпиадных задач (СОЗ) по теории вероятностей и математической статистики (ТВМС) предлагается в качестве учебно-методического пособия прежде всего для студентов и преподавателей ВУЗов как развивающий дополнительный материал, расширяющий ассортимент решаемых задач в лекционной, семинарской и вне аудиторной самостоятельной работе со студентами в различных формах, в том числе и (в соответствии с названием) в проведении олимпиад ...
Добавлено: 9 октября 2026 г.
Человеко-машинная система анализа и улучшения качества условий проживания населения
Алескеров Ф. Т., Вайншток А. П., Делахова А. М. и др., Информационные процессы 2026 Т. 26 № 3 С. 895–913
Проблемы развития и эффективного управления территориальными образованиями являются приоритетными для всех государств, особенно в условиях цифровой трансформации государственного управления. За последнее десятилетие интеграция информационных технологий в муниципальное и региональное планирование существенно изменила подходы к стратегическому развитию, предоставлению услуг и взаимодействию с населением. В данной работе представлено описание функциональности человеко-машинной вебсистемы поддержки принятия решений, в которой ...
Добавлено: 9 октября 2026 г.
Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem
Kupavskii A., Носков Ф. А., Forum of Mathematics, Sigma 2026 Vol. 14 Article 124
Добавлено: 8 октября 2026 г.
Effects of Elevation Changes and Multilevel Structures on Vehicular Signal Propagation
Степанянц В. Г., Andrey V. Fizulin, Chibirov A. и др., FUTURE TRANSPORTATION 2026 Vol. 6 No. 5 Article 225
Добавлено: 8 октября 2026 г.
Modulational Instability and Wave Dynamics in the Rotated Modified Gardner–Whitham Equation
Flamarion M. V., Пелиновский Е. Н., Chaos, Solitons and Fractals 2026 Vol. 213 No. 2 Article 119245
Добавлено: 8 октября 2026 г.
Автоматизированное построение математических теорий
Люксембург А. А., УРСС, 2005.
Изучается возможность автоматизированного построения математических теорий. Рассматривается дедуктивная система, основанная на языке логики предикатов первого порядка, объектами системы являются математические выражения или формулы, которые описывают математические объекты или их свойства. В дедуктивной системе выводятся математические определения и теоремы. Для доказательства теорем используются методы автоматического доказательства. Разработан алгоритм, выводящий часть формул системы. Для решения задачи используется аппарат математической ...
Добавлено: 7 октября 2026 г.
Automated Ranking of Soybean Plots from Close-Range RGB Video via Depth Filtering and Point-Based Counting
Groshev Maksim, Rybakov Petr, Teterin N. и др., Sensors 2026 Article 6171
Добавлено: 7 октября 2026 г.
Decision support system for improving the quality of life of the population
Алескеров Ф. Т., Чайка Е. А., Дерендяев А. Б. и др., Procedia Computer Science 2026 No. 287 P. 590–595
Добавлено: 7 октября 2026 г.
Space-Time Fluctuations in a Quasi-static Limit
Бернардан С. Ж., Gonçalves P., Olla S., Mathematical Physics Analysis and Geometry 2024 Vol. 27 No. 7
Добавлено: 6 октября 2026 г.
Новые информационные технологии в исследовании сложных структур. Материалы шестнадцатой международной конференции 21–25 Сентября 2026 г.
Томск: Издательство Томского государственного университета, 2026.
Материалы сборника Шестнадцатой Международной конференции «Новые информационные технологии в исследовании сложных структур» (Москва, 21–25 сентября 2026 г.) ориентированы на широкий круг специалистов, работающих на стыке теории информации, системного анализа и прикладных предметных областей. В издание вошли результаты исследований, посвящённые моделированию дискретных и стохастических структур управления и связи, разработке высокопроизводительных вычислительных и телекоммуникационных систем, а также вопросам цифровой трансформации образования, архитектурно-градостроительного проектирования,  экологического ...
Добавлено: 6 октября 2026 г.
To spike or not to spike: the whims of the Wonham filter in the strong noise regime
Бернардан С. Ж., Chhaibi R., Najnudel J. и др., Probability Theory and Related Fields 2026 Vol. 195 P. 1823–1875
Добавлено: 5 октября 2026 г.
Цепная дробь Аски–Вильсона при qN=1
Исмаилов А. Р., Спиридонов В. П., Успехи математических наук 2026 Т. 81 № 5 С. 183–184
Получена новая формула для цепной дроби Аски–Вильсона в форме отношения двух  q-гипер-геометрических рядов. ...
Добавлено: 5 октября 2026 г.
О базовых математических определениях цифровых технологий и искусственного интеллекта
Семенов А. Л., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 527 № S С. 7–12
В работе предлагается система определений для основных понятия теории вычислимости, ле­жащих в основе математики цифрового мира: алгоритм, вычислимость, исчисление, сложность объекта, приближенная к современным представлениям. Рассматриваются иерархии конечного и проблема непротиворечивости. ...
Добавлено: 6 декабря 2025 г.
Kolmogorov’s Last Discovery? (Kolmogorov and Algorithmic Statistics)
Семенов А. Л., Шень А., Верещагин Н. К., Theory of Probability and its Applications, USA 2024 Vol. 68 No. 4 P. 582–606
Добавлено: 16 января 2025 г.
On information content in certain objects
Верещагин Н. К., / Series arXiv "math". 2024.
Добавлено: 19 августа 2024 г.
Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time
Баувенс Б. Ф., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9
Добавлено: 22 марта 2023 г.
Information disclosure in the framework of kolmogorov complexity
Верещагин Н. К., Theoretical Computer Science 2023 Vol. 940 P. 108–122
Добавлено: 19 декабря 2022 г.
Predictions and Algorithmic Statistics for Infinite Sequences
Милованов А. С., , 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.
Добавлено: 11 августа 2021 г.
The normalized algorithmic information distance can not be approximated
Баувенс Б. Ф., Блинников И. А., , 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.
Добавлено: 5 февраля 2021 г.
Information Distance Revisited
Баувенс Б. Ф., , 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.
Добавлено: 20 марта 2020 г.
Descriptive complexity of computable sequences revisited
Верещагин Н. К., Theoretical Computer Science 2020 Vol. 809 P. 531–537
Добавлено: 17 января 2020 г.
Algorithmic Statistics: Forty Years Later.
Shen A., Верещагин Н. К., , in: Computability and Complexity.: Berlin: Springer, 2017. P. 669–737.
Добавлено: 26 октября 2018 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору