• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • The Exact Circuit Complexity of Boolean Functions in an Infinite Basis
  • 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 25, 2026
AI Users Earn Up to 41.8% More Than Non-Users
Research conducted by economists at HSE University has revealed a significant correlation between the regular use of GenAI in the workplace and higher pay among Russian employees. The study found that individuals who frequently use GenAI in their professional activities earn notably more than those who reject these new tools or resort to them occasionally. The salary premium for highly qualified specialists reaches 41.8%. The article was published in the Voprosy Ekonomiki journal.
September 24, 2026
‘Feedback and Constructive Criticism Are Essential in Our Profession
Vincent Fardeau, Associate Professor at HSE ICEF, has reached a major career milestone: he recently published his paper ‘Asymmetric Thin Markets’ in the Journal of Financial Economics, successfully passed his major academic review, and received tenure. In this interview, Vincent discusses the story behind the paper, explains the concept of asymmetric thin markets, and shares his advice for young scholars aiming to publish in top-tier journals.
September 22, 2026
Personal Interest in Doctoral Thesis Topic Most Important for Confidence in Successful Defence
A researcher at HSE University analysed data on 1,539 doctoral students from 161 Russian universities to identify which features of a thesis topic are associated with academic success and engagement. The most important factor was found to be personal interest in the research topic, which was associated with almost all key aspects of doctoral programme experience—from engaging with the academic supervisor to research activity and confidence about successfully defending the thesis. The findings have been published in Higher Education.

 

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

?

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

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.

Research target: Mathematics Computer Science
Language: English
Full text
DOI
Text on another site
Keywords: схемная сложностьBoolean circuitsбулевы схемыinfinite basisбесконечный базисinversion complexityинверсионная сложностьlogic circuitsсхемы из функциональных элементов circuit complexityлогические схемы
Similar publications
Lorentzian Principal Bundles with Compact Structure Groups and Causal Properties
Yakovlev E., Maksimov D. A., Mathematical notes 2026 Vol. 120 No. 3 P. 483–496
Smooth principal bundles whose total spaces and bases are time oriented Lorentzian manifolds and whose projections are Lorentzian submersions preserving time orientations are studied. Previously, the authors showed that the chronologicity, causality, and stable causality always lift from the base to the space of a Lorentzian bundle. For strong causality and global hyperbolicity, this holds ...
Added: September 24, 2026
Novikov equations for commuting differential operators of orders 3,4,5
Sokolov V., Shabat G. B., Tsiganov A. V., Journal of Geometry and Physics 2026 Vol. 220
We consider Novikov equations for commutative ring generated by differential operators of orders 3,4,5. We present an explicit Hamiltonian form of these equations. Using the method of compatible Poisson brackets, we find a separation of variables on a hyperelliptic curve of genus 2 for the Novikov equations ...
Added: September 24, 2026
Hadrons in N=2 supersymmetric QCD from non-Abelian string on 2D black hole
Marshakov A., Yung A., Ievlev E. et al., Physical Review D - Particles, Fields, Gravitation and Cosmology 2026 No. 114 P. 1–22
We continue the study of non-Abelian vortex string in 4D N ¼ 2 supersymmetric QCD (SQCD) as critical superstring, and extend this analysis to UðNÞ gauge theory with arbitrary even N and Nf ¼ 2N number of quarks. We introduce a special mass deformation and show that the SQCD hadron spectrum is still given by ...
Added: September 24, 2026
From non-polynomial invariants to non-Liouvillian first integrals
Demina M.V., Nechitailo V., Analysis and Mathematical Physics 2026 Vol. 16 No. 5 P. 1–25
We present a method of finding non-Liouvillian first integrals of rational two-dimensional differential systems. The method is based on the existence of two independent invariants that satisfy a linear second-order ordinary differential equation with respect to one of the variables. We call systems with this property R-integrable. These invariants are not necessarily polynomial; they can ...
Added: September 24, 2026
An Asymptotic Version of the Parametrix Method for Markov Chains Converging to Diffusions
Bitter I., Konakov V., Mathematical notes 2026 Vol. 120 No. 4 P. 599–615
The paper provides a generalization of the local limit theorem on the convergence of inhomogeneous Markov chains to the diffusion limit for the case in which the corresponding coefficients of the process satisfy weak regularity conditions and coincide only asymptotically. In particular, the drift coefficients under consideration can be unbounded with at most linear growth, and the bounds reflect ...
Added: September 24, 2026
Iterative construction of the R-matrices in arbitrary dimensions
Pyatov P. N., Pivovarov P. A., / Series math "arxiv.org". 2026. No. 2609.06274.
We investigate a special ansats that allows for an iterative solution of the constant Yang-Baxter equation. Testing this ansatz, we construct four sequences of the constant R-matrices. In each sequence the R-matrices act on the tensor squares of vector spaces of linearly growing dimensions. Each R-matrix also depends on a single complex parameter. By analyzing the ...
Added: September 24, 2026
Hybrid Graph Retrieval-Augmented Language Agents for Collaborative Recommendation
Ivan Bulychev, Savchenko A., AI 2026 Vol. 7 No. 9 Article 380
Recent advances in large language model (LLM) agents have shown promise for autonomous decision-making in recommender systems. However, existing approaches suffer from two fundamental limitations: flat agent memories that conflate different information modalities and prohibitive computational costs that prevent scaling beyond a few hundred users. We propose Hybrid-GraphRAG, a recommender system that integrates hierarchical agent ...
Added: September 24, 2026
Risks and the image of the future in the study of AI technologies prospects
Snegirev A., Sychev S., Futures 2026 Vol. 183 P. 1–22
This study addresses the systemic identification and categorization of risks associated with AI development, arising from tensions between technological evolution and institutional, infrastructural, and economic contexts. Drawing on a constructionist methodology, we interpret technological risks as constitutive elements of expert communities' images of the future. Through in-depth interviews with 100 AI experts, proportionally representing corporate, ...
Added: September 23, 2026
Choosing Between AI Responses: How Valence, Arousal, and Dominance Shape User Preference
Parshakov P., Paklina S., International Journal of Human-Computer Interaction 2026 P. 1–17
This study examines how emotional tone shapes user preference in human–large language model (LLM) interaction. Drawing on the Computers as Social Actors framework, we treat conversational AI as a social communicator whose affective cues influence user judgments. Using large-scale pairwise preference data from LMSYS Chatbot Arena, we model emotional tone through the Valence–Arousal–Dominance framework and ...
Added: September 23, 2026
A Two-Stage Deep Reinforcement Learning Framework for Radio Resource Management and Network Slicing in 5G Heterogeneous Networks
Andrabi U., Wadood E., Ojha S. K. et al., IEEE Access 2026 Vol. 14 P. 103358–103375
The emergence of 5G networks, aimed at accommodating diverse service requirements such as enhanced Mobile Broadband (eMBB), Ultra-Reliable Low-Latency Communication (URLLC), and massive Machine-Type Communication (mMTC), has presented significant challenges in radio resource management and network slicing. In dynamic heterogeneous network systems, traditional heuristics and mathematical programming methods find it challenging to attain scalable multi-objective ...
Added: September 23, 2026
LLM-assisted writing and citation advantage: evidence from scientific publications before and after ChatGPT release
Paklina S., Parshakov P., Elena Rapoport, Scientometrics 2026 P. 1–26
Generative artificial intelligence has become a routine part of academic writing. While much of the debate has focused on questions of integrity and authorship, less attention has been paid to how AI-assisted writing may affect research evaluation itself. This paper asks a straightforward but important question: does the use of LLMs in academic writing change ...
Added: September 23, 2026
Label-Free Quantification in the Crux Toolkit
Kertesz-Farkas A., Acquaye F. L., Journal of Proteome Research 2026 Vol. 25 P. 3764–3768
Ultimately, most tandem mass spectrometry (MS/MS) proteomics experiments aim to not just detect but also quantify the proteins in a given complex sample. Here, we describe an extension to the Crux MS/MS analysis toolkit to enable label-free quantification of peptides. We demonstrate that Crux’s new quantification command, which is modeled after the algorithms implemented in ...
Added: September 23, 2026
Risk Assessment Models for Heated Tobacco Products
Maddalena L., Yildiz B., Del Vecchio Blanco F. et al., Risk Analysis 2026 Vol. 46 No. 4 P. 1–26
Heated tobacco products (HTPs) are marketed as alternatives to conventional cigarettes with a potential reduced risk profile. Yet, their actual impact on cancer and noncancer disease risk remains uncertain and requires rigorous quantitative assessment. In this study, we develop a unified and transparent computational framework for toxicological risk assessment of HTPs, integrating chemical emissions data ...
Added: September 22, 2026
Обобщение пространства Фока
Дильмухаметова Алия Мидхатовна, Напалков В. В., Муллабаева А. У., Уфимский математический журнал 2010 Т. 2 № 1 С. 52–58
В данной статье введены обобщённые пространства Фока и рассмотрены основные свойства этих пространств. Найдена операция, сопряженная к операции умножения на переменную в обобщенном пространстве Фока. Также определены собственные функции сопряженного оператора. Изучены обобщенное преобразование Лапласа и задача построения базиса для введенных пространств. ...
Added: September 21, 2026
Segmentation of the Iris and Pupil of the Human Eye in Images from an Infrared Camera
Aleksei Samarin, Alexander Savelev, Aleksei Toropov et al., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 855–862
Tasks related to the automation of medical data processing are becoming more urgent. Particular attention is paid to systems for monitoring and analyzing human physiological parameters. Such systems often use specialized sensors to capture biomedical images, such as infrared cameras. This article describes our study of the problem of segmenting the eye pupil and iris ...
Added: September 21, 2026
Точное значение схемной сложности булевых функций в одном бесконечном базисе
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
Математические вопросы кибернетики. Вып. 22
Mikhailovich A., Kochergin V., М.: Физматлит, 2024.
Added: March 10, 2025
Improvement of Nonmonotone Complexity Estimates of k-Valued Logic Functions
Kochergin V., Mikhailovich A., Mathematical notes 2023 Vol. 113 No. 5 P. 794–803
The problem of determining the nonmonotone complexity of the implementation ofk-valued logic functions by logic circuits in bases consisting of all monotone (with respect to thestandard order) functions and finitely many nonmonotone functions is investigated. In calculatingthe complexity measure under examination only those elements of the circuit which are assignednonmonotone basis functions are taken into ...
Added: November 19, 2023
  • 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