?
Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности
Математический сборник. 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]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В настоящей работе дается ответ на этот вопрос: приведен пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности.
Ключевые слова: communication complexityкоммуникационная сложностьHalf-duplex communication complexityполудуплексная коммуникационная сложность
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Алескеров Ф. Т., Вайншток А. П., Делахова А. М. и др., Информационные процессы 2026 Т. 26 № 3 С. 895–913
Проблемы развития и эффективного управления территориальными образованиями являются приоритетными для всех государств, особенно в условиях цифровой трансформации государственного управления. За последнее десятилетие интеграция информационных технологий в муниципальное и региональное планирование существенно изменила подходы к стратегическому развитию, предоставлению услуг и взаимодействию с населением. В данной работе представлено описание функциональности человеко-машинной вебсистемы поддержки принятия решений, в которой ...
Добавлено: 9 октября 2026 г.
Степанянц В. Г., Andrey V. Fizulin, Chibirov A. и др., FUTURE TRANSPORTATION 2026 Vol. 6 No. 5 Article 225
Добавлено: 8 октября 2026 г.
Люксембург А. А., УРСС, 2005.
Изучается возможность автоматизированного построения математических теорий. Рассматривается дедуктивная система, основанная на языке логики предикатов первого порядка, объектами системы являются математические выражения или формулы, которые описывают математические объекты или их свойства. В дедуктивной системе выводятся математические определения и теоремы. Для доказательства теорем используются методы автоматического доказательства. Разработан алгоритм, выводящий часть формул системы. Для решения задачи используется аппарат математической ...
Добавлено: 7 октября 2026 г.
Добавлено: 7 октября 2026 г.
Алескеров Ф. Т., Чайка Е. А., Дерендяев А. Б. и др., Procedia Computer Science 2026 No. 287 P. 590–595
Добавлено: 7 октября 2026 г.
Томск: Издательство Томского государственного университета, 2026.
Материалы сборника Шестнадцатой Международной конференции «Новые информационные
технологии в исследовании сложных структур» (Москва, 21–25 сентября 2026 г.) ориентированы на
широкий круг специалистов, работающих на стыке теории информации, системного анализа и
прикладных предметных областей. В издание вошли результаты исследований, посвящённые
моделированию дискретных и стохастических структур управления и связи, разработке
высокопроизводительных вычислительных и телекоммуникационных систем, а также вопросам
цифровой трансформации образования, архитектурно-градостроительного проектирования,
экологического ...
Добавлено: 6 октября 2026 г.
Серебренников Д. А., Белов А. В., Информационные технологии и вычислительные системы 2026 № 3 С. 157–169
В условиях роста стоимости энергоресурсов и необходимости повышения энергоэффективности производственных процессов особую актуальность приобретает задача оптимизации энергопотребления промышленных предприятий. В данной работе рассматривается подход к управлению энергозатратами машиностроительного предприятия на основе методов многокритериальной оптимизации. Постановка задачи включает несколько целевых функций: минимизацию энергопотребления, минимизацию стоимости электроэнергии с учётом тарифных ограничений и максимизацию производственной эффективности. Для решения ...
Добавлено: 5 октября 2026 г.
Зыков С. В., Уфимцев Г. А., Моделирование, оптимизация и информационные технологии 2026 Т. 14 № 8 С. 1–13
Информационные системы формируют большие объёмы событийных журналов, которые используются для анализа работы приложений и сервисов. При этом события могут поступать в аналитический контур позже момента их фактического возникновения и не в исходном порядке. Такая рассинхронизация приводит к ошибкам при построении агрегированных временных показателей, а регулярный полный пересчёт многомерного аналитического куба требует значительных вычислительных затрат. Целью ...
Добавлено: 2 октября 2026 г.
Polarization of opinions in the group: a modeling algorithm considering the dynamics of social bonds
Chebotarev V., Andreyuk D., Elizarova Anastasiya и др., Procedia Computer Science 2022 Vol. 213 No. C P. 596–601
Добавлено: 2 октября 2026 г.
Konstantinov A., Elizarova Anastasiya P., Utkin L., Computing, Telecommunications and Control 2026 Vol. 19 No. 1 P. 16–25
Деревья решений и их ансамблевые расширения, такие как случайные леса, широко используются в качестве моделей классификации благодаря своей простоте и интерпретируемости. Однако во многих реальных задачах, где метки классов перекрываются в пространстве признаков, стандартные деревья решений полагаются на жесткие разбиения, которые создают слабые границы принятия решений. В этих областях небольшие возмущения входных значений могут привести ...
Добавлено: 2 октября 2026 г.
Prokhorov A., Burda M., Journal of Computational and Graphical Statistics 2026 P. 1–13
Добавлено: 2 октября 2026 г.
Aly Ismailov, Попцова М. С., Plos One 2026 Vol. 21 No. 9 Article e0355902
Добавлено: 2 октября 2026 г.
Злотник А. А., Математические заметки 2026 Т. 120 № 6 С. 1005–1009
Численным методам решения систем газодинамических уравнений посвящена обширная литература. Ранее было разработано и успешно апробировано специальное семейство симметричных по пространству консервативных разностных методов, основанных на предварительной кинетической, точнее, квазигазодинамической (КГД), регуляризации этих уравнений. Актуальной задачей является построение численных методов, которые обладают не только свойством консервативности по массе, импульсу и полной энергии, но и удовлетворяют условиям энтропийной ...
Добавлено: 1 октября 2026 г.
International Joint Conferences on Artificial Intelligence, 2026.
Добавлено: 1 октября 2026 г.
Добавлено: 30 сентября 2026 г.
Джамбонг Тенке Х., Institute for System Programming of the RAS, 2026.
Добавлено: 29 сентября 2026 г.
Игнатьев А. А., 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 г.
Вялый М. Н., 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 г.
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 г.