• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • The Exact Circuit Complexity of Boolean Functions in an Infinite Basis
  • 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
  • еще
Тематика
Новости
14 июля 2026 г.
«Я мечтаю о простых вещах»
Анастасия Гергенретер занимается прикладной статистикой и эконометрикой. В интервью проекту «Молодые ученые Вышки» она рассказала о том, зачем изучает потребление аддиктивных веществ, о двух очень разных Фишерах и о цветении сакуры в Главном ботаническом саду.
14 июля 2026 г.
Ученые НИУ ВШЭ доказали, что машинное обучение может тратить меньше ресурсов
Международная группа исследователей, в которой участвовали математики из Института искусственного интеллекта и цифровых наук ФКН НИУ ВШЭ, теоретически обосновала простой и вычислительно легкий метод оценки неопределенности для стохастического градиентного спуска (SGD). Работа опубликована на сервере научных препринтов arXiv.org и была представлена на AISTATS 2026.
13 июля 2026 г.
Ученые НИУ ВШЭ впервые дали юридическое определение цифровой экосистеме
Цифровые экосистемы за последние годы превратились из технологической инновации в фундаментальный институт современной экономики. По последней оценке НИУ ВШЭ, их вклад в российскую экономику составляет 8,5% ВВП. Однако ни одна юрисдикция не имеет легального определения того, что такое цифровая экосистема. Ученые НИУ ВШЭ закрыли этот пробел, впервые предложив соответствующую правовую концепцию. Статья «Цифровая экосистема как новое экономическое явление и правовая концепция» опубликована в BRICS Law Journal.

 

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

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

?

The Exact Circuit Complexity of Boolean Functions in an Infinite Basis

Mathematical notes. 2025. Vol. 117. No. 4. P. 579–594.
V. V. Kochergin, A. V. Mikhailovich
Научное направление: Математика Компьютерные науки
Язык: английский
Полный текст
DOI
Текст на другом сайте
Ключевые слова: схемная сложностьBoolean circuitsбулевы схемыinfinite basisбесконечный базисinversion complexityинверсионная сложностьlogic circuitsсхемы из функциональных элементов circuit complexityлогические схемы
Похожие публикации
Mathematical Optimization Theory and Operations Research, 25th International Conference, MOTOR 2026 Irkutsk, Russia, July 6–11, 2026 Proceedings
Switzerland: Springer, 2026.
Добавлено: 12 июля 2026 г.
Задачи бесконечной регулярной реализуемости
Шиманогов И. Н., Вялый М. Н., Дискретный анализ и исследование операций 2025 Т. 32 № 4 С. 213–230
Хорошо изученным классом алгоритмических задач являются задачи регулярной реализуемости: проверка непустоты пересечения регулярного языка с заданным языком. Данная задача имеет естественную алгебраическую интерпретацию: проверка принадлежности элемента булевой алгебры ядру определенного гомоморфизма. Это мотивирует рассмотрение аналогичной задачи бесконечной регулярной реализуемости: проверка бесконечности пересечения регулярного языка с заданным. В работе рассматриваются задачи регулярной реализуемости для разрешимых языков ...
Добавлено: 12 июля 2026 г.
Statistical inference based on band-limited kernels: Rational-infinitely divisible distributions and beyond
Панов В. А., Рябченко А. П., / Series arXiv "stat.ME". 2026. No. 2607.05048.
Добавлено: 9 июля 2026 г.
Improving Differential Equation Solving in Compact Language Models via Activation Steering and Reinforcement Learning
Сурков А. Ю., Игнатенко В. В., Koltcov Sergei, Computers, Materials and Continua 2026
Добавлено: 8 июля 2026 г.
Computational Science and Its Applications – ICCSA 2026 Workshops
Springer, 2027.
Добавлено: 8 июля 2026 г.
Conference Proceedings: 2026 IEEE Ural-Siberian Conference on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT), 14-15 May 2026
IEEE, 2026.
Добавлено: 8 июля 2026 г.
Моделирование специализированных алгоритмов маршрутизации в сетях на кристалле, представленных сериями семейств циркулянтных топологий
Маликов М. А., Монахова Э. А., Рзаев Э. Р. и др., Ученые записки Казанского университета. Серия: Физико-математические науки 2026 Т. 168 № 2 С. 269–286
В качестве топологий сетей на кристалле рассмотрены серии семейств оптимальных по диаметру двумерных циркулянтных сетей с прямоугольным контуром укладки на плоскости. Прямоугольный контур укладки графа межмодульных соединений даёт возможность компоновки элементов в сетях на кристалле с минимальным количеством пересечений связей и ограниченной длиной максимальной из них, не зависящей от размера сети. Для серий семейств циркулянтных сетей с ...
Добавлено: 8 июля 2026 г.
Algorithmic overlaps as thermodynamic variables: From local to cluster Monte Carlo dynamics in critical phenomena
Пиле Я. Э., Щур Л. Н., Deng Y., Physical Review B: Condensed Matter and Materials Physics 2026 Vol. 114 Article 014101
Добавлено: 6 июля 2026 г.
Proceedings of the 9th International School-Seminar on Nonlinear Analysis and Extremal Problems (NLA-2026). Irkutsk, Russia, June 22–26, 2026. Irkutsk : ISDCT SB RAS, 2026, 326 p.
Irkutsk: ISDCT SB RAS, 2026.
Добавлено: 5 июля 2026 г.
Журнал Телекоммуникации №1 за 2026
М.: Наука и технологии, 2026.
«Телекоммуникации» ежемесячный рецензируемый производственный, информационно-аналитический и учебно-методический журнал выходит в свет с июля 2000 г. Для руководителей и работников промышленности, научно-исследовательских и проектно-конструкторских институтов, высших учебных заведений, аспирантов и студентов, а также для специалистов, разрабатывающих, выпускающих и эксплуатирующих средства телекоммуникаций. Новости разработок и производства, прогнозы развития, защита информации, Нормативные, справочные, аналитические и учебно-методические материалы. Переход к глобальному информационному ...
Добавлено: 4 июля 2026 г.
"Труды МФТИ" Том 17, № 4 (68) (2025)
МФТИ, 2025.
абота  редакции  научного журнала «Труды Московского физико-технического института» (кратко «Труды МФТИ»), редакционной коллегии и редакционного совета осуществляется в соответствии с Положением, утвержденным ректором института. В состав редакционной коллегии входят руководители института, факультетов, институтских и факультетских кафедр. Главный редактор журнала —президент МФТИ, член-корр. РАН Кудрявцев Н.Н.   Журнал «Труды МФТИ» входит в базу данных РИНЦ (Российский Индекс Научного Цитирования) и доступен в электронной ...
Добавлено: 4 июля 2026 г.
Modulation Recognition for Industrial Internet of Things Communication Signals Under Few-Shot Conditions Based on Attention Mechanism and Relation Network
Hualin M., Jie Z., Jerome Y. и др., Journal of Internet Technology 2026 Vol. 27 No. 3 P. 367–382
Добавлено: 3 июля 2026 г.
Кодовые конструкции на базе обобщенных каскадных кодов для систем связи, использующих прием на основе порядковых статистик
Осипов Д. С., Информационно-управляющие системы 2026 № 3 С. 49–62
Введение: во многих проектируемых в настоящее время и перспективных системах связи методы оценивания характеристик канала и управления мощностью сигнала, разработанные для систем связи предыдущих поколений, не могут обеспечить требуемую точность оценивания и выравнивания мощности сигналов на приемном конце. Одним из вариантов решения этой проблемы является использование методов приема на основе порядковых статистик, которые не требуют управления мощностью ...
Добавлено: 3 июля 2026 г.
Graph Games and Logic Design. Recent Developments and Further Directions. (TREN, volume 66)
Springer, 2026.
Добавлено: 30 июня 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 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика конфиденциальности
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору