?
Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games
Ch. 66.
Игнатьев А. А., Mihajlin I., Smal A.
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022.
V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594
Добавлено: 28 февраля 2026 г.
Верещагин Н. К., Дектярев М. В., Математический сборник 2025 Т. 216 № 6 С. 3–45
Полудуплексная коммуникационная сложность с противником определена в работе [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В ...
Добавлено: 23 августа 2025 г.
Кочергин В. В., Михайлович А. В., Математические заметки 2025 Т. 117 № 4 С. 523–542
Для каждой булевой функции установлено точное значение сложности реализации логическими схемами в бесконечном базисе, состоящем из отрицания и всех монотонных булевых функций. Под сложностью функции понимается минимально возможное число элементов базиса, достаточное для построения схемы для данной функции. ...
Добавлено: 8 апреля 2025 г.
Кочергин В. В., Михайлович А. В., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803
Добавлено: 19 ноября 2023 г.
Alexander Kozachinskiy, Vladimir Podolskii, Theory of Computing 2022 Vol. 18 No. 15 P. 1–33
Добавлено: 10 декабря 2022 г.
Кочергин В. В., Михайлович А. В., В кн.: Материалы XIV Международного семинара "Дискретная математика и ее приложения" имени академика О.Б.Лупанова (Москва, МГУ, 20-25 июня 2022 г.).: М.: Институт прикладной математики им. М.В. Келдыша РАН, 2022. С. 76–79.
Установлена нижняя оценка немонотонной сложности функций многозначной логики, отличающающаяся от известной верхней оценки не более чем на абсолютную константу ...
Добавлено: 29 октября 2022 г.
Кочергин В. В., Чебышевский сборник 2022 Т. 23 № 2(83) С. 121–150
В работе предпринята попытка не только дать обзор результатов, полученных
О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем,
проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций ...
Добавлено: 29 октября 2022 г.
V. V. Kochergin, Moscow University Mathematics Bulletin 2019 Vol. 74 No. 2 P. 43–48
Добавлено: 6 декабря 2021 г.
Вялый М. Н., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160
Добавлено: 20 августа 2021 г.
Подольский В. В., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26
Добавлено: 23 декабря 2020 г.
Подольский В. В., Kulikov A., Theory of Computing Systems 2019 Vol. 63 No. 5 P. 956–986
Добавлено: 9 ноября 2019 г.
V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28–35
Добавлено: 22 апреля 2019 г.
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13–25
Добавлено: 22 апреля 2019 г.
Klenin E., Козачинский А. Н., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–15.
Добавлено: 28 августа 2018 г.
Шитов Я. Н., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653–660
Добавлено: 15 марта 2018 г.
Mikhailovich A.V., Kochergin V.V., Siberian Electronic Mathematical Reports 2017 Vol. 14 P. 1100–1107
Добавлено: 28 сентября 2017 г.
Кочергин В. В., Михайлович А. В., Дискретный анализ и исследование операций 2018 Т. 25 № 1 С. 42–74
Исследуется сложность реализации функций k-значной логики (k > 2) схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т.е. функции x+1 (mod k), и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функии f установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки ...
Добавлено: 28 сентября 2017 г.
Михайлович А. В., Кочергин В. В., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105
Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только ...
Добавлено: 28 сентября 2017 г.
Михайлович А. В., Кочергин В. В., В кн.: Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем".: Улан-Удэ: Издательство Бурятского госуниверситета, 2017. С. 48–52.
Исследуется задача о сложности реализации систем функций k-значной логики схемами из функциональных элементов (логическими схемами) в базисах, состоящих из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан единичный вес. ...
Добавлено: 22 сентября 2017 г.
Михайлович А. В., Кочергин В. В., В кн.: Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.).: М.: МАКС Пресс, 2017. С. 142–144.
Исследуется задача о сложности реализации функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста и всех монотонных функций. ...
Добавлено: 21 сентября 2017 г.