• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groups
  • 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 30, 2026
'We Did Not Limit the Time for Questions'
The International Laboratory for Supercomputer Atomistic Modelling and Multi-Scale Analysis at HSE University held a major conference on molecular dynamics. Participants had the opportunity to attend all the presentations, while speakers were given as much time as they needed to answer questions. The HSE News Service interviewed Grigory Smirnov, Head of the Laboratory, and Genri Norman, Chief Research Fellow, about the conference preparations and the discussions it generated.
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.

 

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

?

Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groups

Moscow University Mathematics Bulletin. 2022. Vol. 77. No. 3. P. 113–119.
Kochergin V.

Abstract: The computational complexity of the element (Formula presented.) of the Abelian group (Formula presented.) (it is supposed that kii for all i) and the computational complexity of the term (Formula presented.) are compared in the paper. The computational complexity means the minimal possible number of multiplication operations, and all the results of intermediate multiplications can be used multiple times. It is established that, if (Formula presented.), then the maximal possible difference and ratio of the above values asymptotically grow for (Formula presented.) as (Formula presented.) and (Formula presented.), respectively. © 2022, Pleiades Publishing, Inc.

Research target: Mathematics Computer Science
Language: English
DOI
Keywords: Computational ComplexityAddition chainsvectorial addition chainsfinite Abelian groupBellman’s problemKnuth’s problem
Similar publications
Role of dislocations in the mobility of pinned helium bubbles: Molecular dynamics simulations in aluminum
Piliugin L., Antropov A., Lobashev E. et al., Journal of Nuclear Materials 2026 Vol. 632 Article 156876
The effects of dislocations on the mobility of gas nanobubbles pinned to them are considered as novel unex- plored mechanisms of accelerated fission gas release and investigated using classical molecular dynamics of helium bubbles in FCC aluminum. Non-equilibrium methods are developed to calculate the mobility of a pinned bubble both along and across the dislocation ...
Added: September 28, 2026
MPI+OpenMP implementation of resolution-of-the-identity Hartree-Fock method exploiting permutational symmetry of three-center electron repulsion integrals
Kashpurovich I., Oleynichenko A., Stegailov V., Supercomputing Frontiers and Innovations 2026 Vol. 13 No. 1 P. 52–73
We report a high-performance implementation of the resolution-of-the-identity Hartree–Fock method that fully exploits the permutational symmetry of three-center electron repulsion integrals (ERI). The present implementation adopts a hybrid MPI+OpenMP parallelization strategy. Two different algorithmic approaches (with and without the pre-transformation of ERIs) are compared. A custom data layout introduced previously is employed. Designed to efficiently ...
Added: September 28, 2026
A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection
Teregulov T., Loubenets E. R., / Series Quantum Physics "arXiv". 2026. No. 2609.31472.
We develop a new three-party quantum secret-sharing (QSS) protocol based on a three-qubit W state. This protocol encodes the secret-sequence bits using X gates and employs randomly selected Hadamard operations and measurement bases to generate information and security-test rounds. We evaluate the efficiency of the proposed protocol and analyze its security against an internal adversary ...
Added: September 28, 2026
Bytedance и Open Source - открытые проекты от разработчика TikTok
Silakov D., Системный администратор 2026 С. 84–89
Social media users rarely think about what lies behind the beautiful facade of activity feeds, teeming with photos and video stories. However, the widespread popularity of such platforms generates a huge amount of all sorts of content that needs to be stored, processed quickly, and displayed, and in the era of AI, it also needs ...
Added: September 28, 2026
Shape-aware deep learning for models of production
Prokhorov A., Wei Z., Sang H. et al., Journal of Productivity Analysis 2026 Vol. 65 P. 1–16
The stochastic frontier model (SFM) is widely employed in the analysis of productivity and efficiency, yet strict parametric forms, such as the Cobb-Douglas and Translog functions, are often assumed for modeling production, leading to potential misspecification issues. While semi- and nonparametric SFMs offer greater flexibility, they face challenges in imposing monotonicity and concavity to maintain ...
Added: September 28, 2026
Hamiltonian Sets of Polygonal Paths in Assembly Graphs
Guterman A., Jonoska N., Kreines E. et al., Proceedings of the Edinburgh Mathematical Society 2026 Vol. 69 No. 3 P. 1041–1057
We provide four equivalent combinatorial conditions for a simple assembly graph (rigid vertex graph where all vertices are of degree 1 or 4) to have the largest number of Hamiltonian sets of polygonal paths relative to its size. These conditions serve to prove the conjecture that such a maximum, which is equal to 𝐹_(2⁢𝑛+1) −1, ...
Added: September 27, 2026
Inverse quickest path problem on networks under weighted l_\infty norm
Qian X., Guan X., Zhang B. et al., Journal of Global Optimization 2026
Inverse quickest path problem on networks ...
Added: September 27, 2026
О приложениях обобщённого потенциала Бесселя к решению сингулярного уравнения Шрёдингера дробного порядка и теории ёмкости
Shishkina E., Современная математика. Фундаментальные направления 2026 Т. 72 № 1 С. 52–67
In this paper, we construct a weighted Sobolev space of fractional order based on the generalized Bessel potential.We apply these results to the analysis of the singular fractional Schr¨odinger equation. To solve the Cauchy problem for this equation, we prove an estimate that relates the norm of the solution to the norm of the initial condition in the ...
Added: September 26, 2026
A Semigroup Approach for Constructing the Fractional Power of the Laplace–Bessel Operator
Shishkina E., Computational Mathematics and Mathematical Physics 2026 Vol. 66 No. 5 P. 804–815
This article demonstrates that the Laplace–Bessel operator generates a strongly continuous semigroup on a weighted Lebesgue space. Using this semigroup, we define the fractional Laplace– Bessel operator via Balakrishnan’s formula. Furthermore, we derive three distinct representations for fractional powers of the negative Laplace–Bessel operator. ...
Added: September 26, 2026
Matrix Approach To The Fractional Calculus
Kolokoltsov V., Shishkina E., Journal of Theoretical Probability 2026 P. 39–83
In this paper, we introduce a new construction of fractional derivatives and integrals with respect to a function, based on a matrix approach. We believe that this is a powerful tool in both analytical and numerical calculations.We begin with the differential operator with respect to a function that generates a semigroup. By discretizing this operator, we obtain a matrix ...
Added: September 26, 2026
Navigating Complexity: Statistical Methods, Data Analysis, and Machine Learning for Actionable Insights
Switzerland: Springer Cham, 2026.
This volume gathers selected, peer-reviewed contributions presented at the 19th Conference of the International Federation of Classification Societies (IFCS 2026), held on 14–16 July 2026 in Milan, Italy. Reflecting the volume’s motto, Navigating Complexity – Statistical Methods, Data Analysis, and Machine Learning for Actionable Insights, the papers showcase modern methodologies and real-world applications designed to extract ...
Added: September 25, 2026
AN ANALOGUE OF ROGERS’ THEOREM ON SIEVING IN COMMUTATIVE RINGS
Petr Kucheriaviy, Bulletin of the Australian Mathematical Society 2026
We prove that an analogue of Rogers’ theorem on sieving holds for an order if and only if the order is a Dedekind domain. We also prove that it holds for a finite commutative ring if and only if the ring is a direct product of local rings with linearly ordered ideals. ...
Added: September 25, 2026
An early warning system for emerging markets
Kraevskiy A., Sokolovskiy E., Prokhorov A., Emerging Markets Review 2026 No. 74 P. 1–19
Financial markets of emerging economies are vulnerable to extreme and cascading information spillovers, surges, sudden stops and reversals. With this in mind, we develop a new online early warning system (EWS) to detect what is referred to as ‘concept drift’ in machine learning, as a ‘regime shift’ in economics and as a ‘change-point’ in statistics. ...
Added: September 25, 2026
Билинейные теоремы сложения и последовательности Сомоса
Пелевин Ф. Е., Математические заметки 2026 Т. 120 № 1 С. 159–163
Две не равные тождественно нулю функции (последовательности элементов некоторого поля) будем называть эквивалентными, если они удовлетворяют функциональному уравнению типа теорем сложения тэта-функций. Основной результат работы состоит в том, что рассматриваемое отношение действительно является отношением эквивалентности. ...
Added: September 25, 2026
Computable isomorphisms of relative regular Boolean algebras
Shimanogov I. N., Vyalyi M., Siberian Mathematical Journal 2026 Vol. 67 No. 5 P. 1203–1212
We consider a class of Boolean algebras formed by intersections of regular languages with a given language. In the case where such an algebra is isomorphic to the algebra of regular languages, we prove the existence of an isomorphism that is computable using oracles for the regular realizability problem and the infinite regular realizability problem. This result yields ...
Added: September 25, 2026
Экспериментальное сравнение HTTP/2 и HTTP/3 в условиях программно моделируемой сетевой деградации
Дубич Е. В., Schagin D., Славянский форум 2026 № 2 (52) С. 560–565
The paper compares HTTP/2 and HTTP/3 for static resource transfer under software-simulated network degradation. The experiment shows that HTTP/3 is not universally faster, but it is more stable as latency and packet loss increase. ...
Added: September 25, 2026
Dual role of Poisson impulses in Hindmarsh–Rose networks: Disorder, pattern formation, and synchronization
Ramazanov I., Bukh A., Shepelev Igor A., Chaos 2026 No. 36 P. 083150–083150
We investigate how stochastic Poisson impulsive forcing influences the spatiotemporal dynamics of a two-dimensional network of Hindmarsh–Rose neurons. Unlike continuous noise, impulsive forcing introduces discrete, state-dependent perturbations, making the system response highly sensitive to both the statistics and the spatial structure of the input. In most of the parameter space, stochastic impulses destabilize the initial ...
Added: September 24, 2026
Synthesis of Acyclic Models for Processes Without Repeating Events
Joulitov A.K., Lomazova I.A., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 4(2) P. 215–224
In process mining, DFG (Directly-Follows Graph) models are popular due to their simplicity and clarity. However, if a process is acyclic but contains concurrent events, standard algorithms for discovering DFG models can generate "fake" cycles that do not actually exist in the event log. These cycles hinder the analysis of information processes, significantly reducing the ...
Added: September 24, 2026
Анализ протокола выработки общего ключа для управления микросхемой интеллектуальной карты
Добрина Д. Н., Nesterenko A., Прикладная дискретная математика. Приложение 2026 № 19 С. 151–159
Работа содержит результаты формального анализа криптографических механизмов, входящих в состав проекта методических рекомендаций «Защищенный универсальный протокол передачи данных и управления микросхемой интеллектуальной карты» (протокол SECUNDA). Получена формальная модель и перечень трудноразрешимых математических задач, трудоёмкостью решения которых можно оценить стойкость используемых криптографических механизмов. ...
Added: September 24, 2026
Конечные абелевы подгруппы в группах бирациональных и бимероморфных автоморфизмов
Golota A., Известия РАН. Серия математическая 2024 Т. 88 № 5 С. 47–66
Let X be a complex projective variety. Suppose that the group of birational automorphisms of X contains finite subgroups isomorphic to (Z/NZ)^r for r fixed and N arbitrarily large. We show that r does not exceed 2dim(X). Moreover, the equality holds if and only if X is birational to an abelian variety. We also show that an analogous ...
Added: November 6, 2024
On efficient algorithms for bottleneck path problems with many sources
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or max min ) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise ...
Added: April 18, 2024
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain ...
Added: February 16, 2024
Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering with a Covering Axiom
Gerasimova O., Makarov I., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Added: January 5, 2024
The discrete Fourier transform over the binary finite field
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779
The novel methods for binary discrete Fourier transform (DFT) computation over the finite field have been proposed. The methods are based on a binary trace calculation over the finite field and use the cyclotomic DFT. The direct DFT computational complexity has been reduced due to using the binary trace function over the finite field and ...
Added: July 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