• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Об оценках сложности схем в одном бесконечном базисе
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 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
  • More
Subject
News
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Об оценках сложности схем в одном бесконечном базисе

С. 97–100.
Podolskaya O.
We study Boolean circuit complexity in an infinite basis consisting of all Boolean functions that equal 1 only on sets of pair-wise incomparable tuples. It is known that lower bounds on the complexity of linear function, majority function and almost all boolean functions of $n$ variables are of the order $\sqrt n.$ We show that the complexity of any $n$-variable Boolean function is at most $n$ in this basis.
Language: Russian
Text on another site
Keywords: upper boundUpper boundBoolean circuit complexityBoolean circuitsantichain functionбулевы схемыантицепная функцияinfinite basisбесконечный базиссложность схемверхняя оценка

In book

Материалы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.)
М.: Издательство ИПМ РАН, 2013.
Similar publications
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
The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. ...
Added: February 28, 2026
A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks
Monakhova E., Monakhov O., Edward R. Rzaev et al., IEEE Access 2025 Vol. 13 P. 104716–104727
Based on the analysis of a large dataset for optimal undirected double-loop networks, we studied the problem of finding families of optimal double-loop graphs with the minimal possible diameter. Optimal double-loop networks are of practical interest as graph models for reliable, low-delay communication in computer systems and networks-on-chip, due to their advantageous networking properties. A ...
Added: June 30, 2025
Точное значение схемной сложности булевых функций в одном бесконечном базисе
Kochergin V., Mikhailovich A., Математические заметки 2025 Т. 117 № 4 С. 523–542
The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function. ...
Added: April 8, 2025
Верхняя оценка спектральной эффективности для систем с гибридной решающей обратной связью при ограничении на вид модуляции
Бурков А. А., Tyurlikov A., Вопросы радиоэлектроники. Серия: Техника телевидения 2020 № 1 С. 74–83
A transmission system with a hybrid automatic repeat request is considered in the presence of slow Rayleigh fading. A technique is described for finding an upper estimation of the spectral efficiency for such a system with a restriction on the type of modulation. Estimation can be used in the analysis of developed and existing feedback ...
Added: September 26, 2023
О работах О. М. Касим-Заде в области теории сложности и теории многозначных логик
Kochergin V., Чебышевский сборник 2022 Т. 23 № 2(83) С. 121–150
В работе предпринята попытка не только дать обзор результатов, полученных О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем, проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций ...
Added: October 29, 2022
Arbitrarily accurate approximation of numerical characteristics of stationary ALOHA Channels
Burkov A. A., Shneer S., Turlikov A. M., , in: WAVE ELECTRONICS AND ITS APPLICATION IN INFORMATION AND TELECOMMUNICATION SYSTEMS. 2021. (WECONF 2021) St. Petersburg, Russia, 31 May - 4 June 2021.: IEEE, 2021. Ch. 9470700 P. 1–8.
The development of the Internet of Things technology in cellular networks is considered within the framework of massive machine-type communications with the use of random multiple access algorithms such as ALOHA and its modifications. Despite the fact that this class of algorithms has been studied for a long time, there are no numerical methods for ...
Added: October 28, 2022
О сложности систем функций k-значной логики в двух бесконечных базисах
Mikhailovich A., Kochergin V., В кн.: Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова.: Изд-во механико-математического факультета МГУ, 2019. С. 129–131.
Added: December 7, 2021
О немонотонной сложности функций k-значной логики
Kochergin V., Mikhailovich A., В кн.: Проблемы теоретической кибернетики. Материалы заочного семинара XIX международной конференции.: Издательство Казанского (Приволжского) федерального университета, 2021. С. 75–78.
В работе исследуется сложность реализации функций многозначной логики над базисами, содержащими все монотонные функции и конечное число немонотонных функций. Получены верхняя и нижняя оценка, отличающиеся на константу, не зависящую от базиса. ...
Added: December 6, 2021
Оценки немонотонной сложности функций многозначной логики
Kochergin V., Mikhailovich A., Ученые записки Казанского университета. Серия: Физико-математические науки 2020 Т. 162 № 3 С. 311–321
The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is ...
Added: December 6, 2021
Алгоритмы синтеза схем-заплаток для решения ресурсо-ориентированной функциональной коррекции схем из функциональных элементов
Высоцкий Л. И., Жуков В. В., Шуплецов М. С., В кн.: Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018)Вып. 1.: М.: ИППМ РАН, 2018. С. 30–37.
При обнаружении ошибок или изменении спецификации проектируемой сверхбольшой интегральной схемы (СБИС) на поздних этапах маршрута проектирования откат на более ранние этапы проектирования и их повторное выполнение очень часто становится непрактичным в силу существенных временных затрат. Для целей сокращения времени проектирования в современные маршруты проектирования интегрируют специальные этапы функциональной коррекции схемы (англ. Engineering Change Order, ECO). В основе указанного подхода лежит анализ уже спроектированной схемы и построение небольшой подсхемы-заплатки, внедрение которой в уже синтезированную ...
Added: November 10, 2020
О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2014 Т. 3 № 31 С. 78–100
Background The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
Об одновременной оптимизации формул по сложности и задержке на наборах в модели с задержками соединений между элементами
Danilov B. R., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58–77
Background The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem ...
Added: December 2, 2019
Асимптотические оценки функции Шеннона в одной модели глубины схем из функциональных элементов с емкостными параметрами выходов элементов
Danilov B. R., Ложкин С. А., Прикладная математика и информатика 2018 № 59 С. 40–49
В работе предлагается метод синтеза усилительных схем из функциональных элементов (УСФЭ), позволяющий установить асимптотику функции Шеннона для обобщённой глубины УСФЭ – то есть глубины самой «плохой» функции алгебры логики, зависящей от заданных   переменных – в специальном базисе (модели глубины), где глубина элемента определяется как его типом, так и степенью ветвления выхода в схеме. Асимптотическое поведение ...
Added: December 2, 2019
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit