Нижняя оценка немонотонной сложности функций многозначной логики

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

20 августа 2026 г.

<a>Исследователи НИУ ВШЭ и Сбера научили нейросети лучше угадывать предпочтения пользователей

Институт искусственного интеллекта и цифровых наук ФКН НИУ ВШЭ и Сбер представили новую архитектуру для рекомендательных систем: благодаря объединению двух классов моделей алгоритмы лучше угадывают интересы и потребности пользователей. Препринт работы опубликован на сайте arxiv.org и представлен на летнем фестивале «Урбан ML».

19 августа 2026 г.

Ученые ВШЭ разработали алгоритм, позволяющий производить более надежные процессоры для ЦОД

Ученые из МИЭМ ВШЭ и Самарского университета создали алгоритм LRF-3D для автоматического обхода неработающих узлов в трехмерных сетях на кристалле. Благодаря своей иерархической организации он превосходит аналоги по быстродействию и точности пути, повышая надежность процессоров для использования в ЦОД, суперкомпьютерах и ИИ-вычислениях. Исходные коды алгоритмов и тестов опубликованы в открытом доступе.

13 августа 2026 г.

Социальная интеграция: на перекрестках знаний и ценностей

Международная лаборатория исследований социальной интеграции (МЛИСИ) НИУ ВШЭ занимается изучением проблем уязвимых слоев населения и поиском методов их вовлечения в полноценную повседневную жизнь. Для поиска решений ученые лаборатории сочетают разработку передовых методов с практической работой «в поле». О деятельности лаборатории новостной службе «Вышка.Главное» рассказала ее заведующая Елена Ярская-Смирнова.

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

Публикации

?

Нижняя оценка немонотонной сложности функций многозначной логики

С. 76–79.

Кочергин В. В., Михайлович А. В.

Установлена нижняя оценка немонотонной сложности функций многозначной логики, отличающающаяся от известной верхней оценки не более чем на абсолютную константу

Язык: русский

В книге

Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.)

М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022.

The Exact Circuit Complexity of Boolean Functions in an Infinite Basis

V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594

Добавлено: 28 февраля 2026 г.

Точное значение схемной сложности булевых функций в одном бесконечном базисе

Кочергин В. В., Михайлович А. В., Математические заметки 2025 Т. 117 № 4 С. 523–542

Для каждой булевой функции установлено точное значение сложности реализации логическими схемами в бесконечном базисе, состоящем из отрицания и всех монотонных булевых функций. Под сложностью функции понимается минимально возможное число элементов базиса, достаточное для построения схемы для данной функции. ...

Добавлено: 8 апреля 2025 г.

Математические вопросы кибернетики. Вып. 22

Михайлович А. В., Кочергин В. В., М.: Физматлит, 2024.

Добавлено: 10 марта 2025 г.

Improvement of Nonmonotone Complexity Estimates of k-Valued Logic Functions

Кочергин В. В., Михайлович А. В., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803

Добавлено: 19 ноября 2023 г.

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Игнатьев А. А., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.

Добавлено: 9 ноября 2023 г.

Сравнение оценок сложности для задач Р. Беллмана и О. Б. Лупанова

Кочергин В. В., В кн.: Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.).: М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 4–16.

Задача Беллмана является обобщением классической задачи об эффективном возведении в степень, т.\,е. задачи о нахождении величины $l(x^n)$ --- минимального числа операций умножения, достаточного для вычисления по переменной $x$ величины $x^n$, при этом вычислительная модель допускает возможность многократного использования результатов промежуточных вычислений. Задача Лупанова заключается в нахождении сложности вычисления элемента конечной абелевой группы по ее образующим. Значение ...

Добавлено: 29 октября 2022 г.