• 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
  • 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
June 5, 2026
Neural Network Maps as a Method for Constructing Mathematical Models
Scientists from HSE University–Nizhny Novgorod and the Institute of Physics Belgrade, Serbia, are jointly exploring the application of machine learning techniques and neural networks to the study of nonlinear dynamics. Natalya Stankevich, Leading Research Fellow at the Laboratory of Topological Methods in Dynamics of the Faculty of Informatics, Mathematics, and Computer Science at HSE University–Nizhny Novgorod, spoke to the HSE News Service about this international project.
June 5, 2026
‘In the Age of Technology, It Is Interesting to Look into the Past and Think about What We Can Take from It
Polina Tabakova decided to apply for a Philology degree at HSE in Nizhny Novgorod because she grew up in Mari El and did not want to move far away from the Russian forests. In an interview for the Young Scientists of HSE University project, she spoke about the genre of the campus novel, the existential drama of Kolobok, and a blackout version of Eugene Onegin.
June 5, 2026
HSE Scientists Develop Method to Compress Large Language Models Without Losing Quality
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science have developed a new compression method for large language models such as GPT and LLaMA that reduces their size by 25–36% without additional training or significant loss of accuracy. This is the first approach to use mathematical transformations—specifically, rotations of model weights—to make models more amenable to compression with structured matrices. The study results have been published in ACL Findings 2025. The code is available on GitHub.

 

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

?

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

С. 56–58.
Podolskaya O.
Language: Russian
Text on another site
Keywords: symmetric functionsсимметрическая булева функцияBoolean circuitBoolean circuit complexityantichain functionантицепная функцияinfinite basisбесконечный базиссложность схемсхемы из функциональных элементов

In book

Материалы X молодежной научной школы по дискретной математике и ее приложениям
М.: Издательство ИПМ РАН, 2015.
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
Симметрические функции. Начальный курс
Smirnov E., Тутубалина А. А., М.: МЦНМО, 2026.
Книга написана по материалам семестрового курса «Симметрические функции», читавшегося авторами в Независимом московском университете и на факультете математики Высшей школы экономики. В ней излагаются как классические, так и недавние результаты о симметрических функциях и их обобщениях, причем основное внимание уделяется комбинаторным аспектам теории. Курс снабжен большим количеством задач и упражнений, ко многим из которых приводятся ...
Added: December 2, 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
О работах О. М. Касим-Заде в области теории сложности и теории многозначных логик
Kochergin V., Чебышевский сборник 2022 Т. 23 № 2(83) С. 121–150
В работе предпринята попытка не только дать обзор результатов, полученных О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем, проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций ...
Added: October 29, 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
Слайд-многочлены и комплексы подслов
Smirnov E., Тутубалина А. А., Математический сборник 2021 Т. 212 № 10 С. 131–151
Subword complexes were defined by A.Knutson and E.Miller in 2004 for describing Gröbner degenerations of matrix Schubert varieties. The facets of such a complex are indexed by pipe dreams, or, equivalently, by the monomials in the corresponding Schubert polynomial. In 2017 S.Assaf and D.Searles defined a basis of slide polynomials, generalizing Stanley symmetric functions, and ...
Added: September 29, 2021
Elements of the q-Askey Scheme in the Algebra of Symmetric Functions
Olshanski G., Cuenca C., Moscow Mathematical Journal 2020 Vol. 20 No. 4 P. 645–694
The classical q-hypergeometric orthogonal polynomials are assembled into a hierarchy called the q-Askey scheme. At the top of the hierarchy, there are two closely related families, the Askey–Wilson and q -Racah polynomials. As it is well known, their construction admits a generalization leading to remarkable orthogonal symmetric polynomials in several variables. We construct an analogue of the ...
Added: January 19, 2021
Алгоритмы синтеза схем-заплаток для решения ресурсо-ориентированной функциональной коррекции схем из функциональных элементов
Высоцкий Л. И., Жуков В. В., Шуплецов М. С., В кн.: Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018)Вып. 1.: М.: ИППМ РАН, 2018. С. 30–37.
При обнаружении ошибок или изменении спецификации проектируемой сверхбольшой интегральной схемы (СБИС) на поздних этапах маршрута проектирования откат на более ранние этапы проектирования и их повторное выполнение очень часто становится непрактичным в силу существенных временных затрат. Для целей сокращения времени проектирования в современные маршруты проектирования интегрируют специальные этапы функциональной коррекции схемы (англ. Engineering Change Order, ECO). В основе указанного подхода лежит анализ уже спроектированной схемы и построение небольшой подсхемы-заплатки, внедрение которой в уже синтезированную ...
Added: November 10, 2020
Asymptotic Bounds of the Shannon Function for a Depth Model of Functional-Element Networks With Capacity Parameters for Element Outputs
Danilov B.R., Lozhkin S. A., Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 129–136
The article proposes a synthesis method for amplifying networks of functional elements (ANFE) that establishes the asymptotic behavior of the Shannon function for th ANFE generalized depth, i.e., the depth of the "worst" Boolean function of n given variables, in a special basis (the depth model) where the element depth is determined both by its ...
Added: December 1, 2019
Interpolation Macdonald polynomials and Cauchy-type identities
Olshanski G., Journal of Combinatorial Theory, Series A 2019 Vol. 162 P. 65–117
Let Sym denote the algebra of symmetric functions and P_μ( · ; q, t) and Q_μ( · ; q, t) be the Macdonald symmetric functions (recall that they differ by scalar factors only). The (q, t)-Cauchy identity expresses the fact that the P_μ( · ; q, t)’s form an orthogonal basis in Sym with respect to ...
Added: May 25, 2019
Exact Value of the Nonmonotone Complexity of Boolean Functions
V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28–35
We study the complexity of the realization of Boolean functions by circuits in infinite complete bases containing all monotone functions with zero weight (cost of use) and finitely many nonmonotone functions with unit weight. The complexity of the realization of Boolean functions in the case where the only nonmonotone element of the basis is negation ...
Added: April 22, 2019
Circuit complexity of k-valued logic functions in one infinite basis
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13–25
We investigate the realization complexity of k-valued logic functions k ≥ 2 by combinational circuits in an infinite basis that includes the negation of the Lukasiewicz function, i.e., the function k−1−x, and all monotone functions. Complexity is understood as the total number of circuit elements. For an arbitrary function f, we establish lower and upper ...
Added: April 22, 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