Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems

?

Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems

Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций"). 2015. Vol. 9. No. 1. P. 68–82.

Kochergin V. V.

We study two generalizations of the classical problem of fast exponentiation, namely: Bellman’s problemon computational complexity (the minimal number ofmultiplications) based only on the variables of a normalized monomial of m variables and Knuth’s problem on the complexity of the simultaneous calculation of a system of m powers of one variable. Some results for these problems are reviewed in the paper. The asymptotic complexity bounds for Bellman’s and Knuth’s problems are improved for the cases whenmand complexity behave similarly (have the same growth order). The upper and lower complexity bounds for almost all sets of exponents for Bellman’s and Knuth’s problems that are established provide the complexity growth asymptotics for a wide range of relations between parameters (the number of variables or the computed exponents, the maximal power, and the product of all powers). Moreover, they guarantee the ratio of the upper and lower bounds not exceeding 5/3 for all relations between the parameters.

Research target: Mathematics

Priority areas: mathematics

Language: English

DOI

The Sobolev space W_2^{1/2}: Simultaneous improvement of functions by a homeomorphism of the circle

Lebedev V., Journal of Mathematical Analysis and Applications 2026 Vol. 563 No. 2 Article 130787

It is known that for every continuous real-valued function $f$ on the circle $\mathbb T=\mathbb R/2\pi\mathbb Z$ there exists a change of variable, i.e., a self-homeomorphism $h$ of $\mathbb T$, such that the superposition $f\circ h$ is in the Sobolev space $W_2^{1/2}(\mathbb T)$. We obtain new results on simultaneous improvement of functions by a single change of variable in relation ...

Added: May 14, 2026

Symmetric Cubic Polynomials

Blokh A., Oversteegen L., Selinger N. et al., Arnold Mathematical Journal 2025 Vol. 12 No. 1 P. 1–40

We describe a model for the boundary of the connectedness locus of the parameter space of cubic symmetric polynomials. We show that there exists a monotone continuous function from the connectedness locus to the model which is a homeomorphism if the former is locally connected. ...

Added: May 13, 2026

Игры на сетях с линейным наилучшим ответом: модели и методы управления

Petrov I., Автоматика и телемеханика 2026 № 6 С. 82–118

Системам связанных агентов и сетевому управлению посвящено большое число отечественных и зарубежных исследований. Исторически, наибольший интерес в теории управления возникал к усредняющим системам и, в частности, к задаче консенсуса. Однако сетевое взаимодействие может характеризоваться более специфическими функциями, отражающими зависимость от действий соседей по сети, что особенно явно проявляется в моделях стратегического взаимодействия на сети, которое ...

Added: May 12, 2026

Архимед: научно-методический сборник

М.: ООО «Макс Пресс», 2026.

В настоящем сборнике представлены тезисы докладов участников семинара "Интеграция основного и дополнительного физико-математического образования", проходившего 11 февраля 2026 года в ГБОУ Школа №2007 ФМШ г. москвы, а также другие публикации, посвящённые вопросам дополнительного физико-математического образования. ...

Added: May 11, 2026

A two-point phase recovering from holographic data on a single plane

Novikov R., Sivkin V., Inverse Problems 2026 Vol. 42 No. 4 Article 045009

We consider a plane wave, a radiation solution, and the sum of these solutions (total solution) for the Helmholtz equation in an exterior region in Rd, d ⩾ 2. In this region, we consider a hyperplane X with sufficiently large distance s from the origin in Rd. We give two-point local formulas for approximate recovering the radiation ...

Added: May 11, 2026

Multivariate Newton interpolation in downward closed spaces reaches the optimal Bernstein–Walsh approximation rate

Hecht M., Hofmann P., Wicaksono D. et al., IMA Journal of Numerical Analysis 2026 Vol. 00 P. 1–30

Recent advances in Bernstein—Walsh theory have extended Bernstein’s Theorem to multiple dimensions, stating that a multivariate function can be approximated with a geometric rate in a downward-closed polynomial space if and only if it is analytic in a generalized Bernstein polyellipse. To compute approximations of this class of functions—which we term Bos–Levenberg–Trefethen–(BLT) functions—we extend the ...

Added: May 11, 2026

Weighted Chernoff Information and Optimal Loss Exponent in Context-Sensitive Hypothesis Testing

Kelbert M., Kalimulina E. Y., Entropy 2026 Vol. 28 Article 536

We study binary hypothesis testing for i.i.d. observations under a multiplicative context weight. For the optimal weighted total loss, defined as the sum of weighted type-I and typeII losses, we prove the logarithmic asymptotic L∗n = exp{−nDwC (P,Q) + o(n)}, n →∞, where Dw C is the weighted Chernoff information. The single-letter form of the exponent relies on ...

Added: May 7, 2026

Calogero–Sutherland hyperbolic system and Heckman–Opdam $$\mathfrak {gl}_n$$ gl n hypergeometric function

Белоусов Н. М., Черепанов Л. К., Деркачов С. Э. et al., Selecta Mathematica, New Series 2026 Vol. 32 Article 44

We prove equivalence of two integral representations for the wave functions of hyperbolic Calogero–Sutherland system. For this we study two families of Baxter operators related to hyperbolic Calogero–Sutherland and rational Ruijsenaars models; the first one as a limit from hyperbolic Ruijsenaars system, while the second one independently. Besides, computing asymptotics of integral representations and also ...

Added: May 6, 2026

Hodge Laplacian Eigenvalues on Surfaces with Boundary

Муравьев М. Ю., Annales Mathematiques du Quebec 2025

Recently Rohleder proposed a new variational approach to an inequality between the Neumann and Dirichlet eigenvalues in the simply connected planar case using the language of classical vector analysis. Interpreting his approach in terms of differential forms permits to generalize these results to a much broader context. The spectrum of the absolute boundary problem for ...

Added: May 6, 2026

Об изоморфизме задачи Козлова о движении ферромагнетика в магнитном поле и задачи Шоттки о движении четырехмерного твердого тела

Цыганов А. В., Порубов Е. О., Теоретическая и математическая физика 2026 Т. 227 № 2 С. 336–355

Теория тензорных инвариантов обыкновенных дифференциальных уравнений и классификация Картана простых алгебр Ли используется для установления изоморфизма задачи Козлова о движении ферромагнетика в магнитном поле и задачи Шоттки о движении четырехмерного твердого тела. Найдены новые полиномиальные и рациональные бивекторы Пуассона, инвариантные либо относительно пары коммутирующих фазовых потоков, либо относительно одного из пары потоков. ...

Added: May 5, 2026

Моделирование и оценка ресурсных затрат алгоритмов маршрутизации в сетях на кристалле с двумерной циркулянтной топологией

Монахова Э. А., Монахов О. Г., Rzaev E. et al., Прикладная дискретная математика 2026 Т. 71 С. 112–127

В настоящей работе исследовано совместное конструирование топологий семейств оптимальных по диаметру циркулянтных сетей $C(N; \pm 1, \pm s_2)$ и реализуемых для них оптимальных алгоритмов маршрутизации сложности $O(1)$. Предлагаемый алгоритм маршрутизации основан на использовании масштабируемых параметров $L$-образных шаблонов плотной укладки графов на плоскости для семейств оптимальных сетей. Определены аналитические формулы зависимости этих параметров от диаметра графов семейств ...

Added: May 4, 2026

On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces

Dudakov S., Lobachevskii Journal of Mathematics 2025 Vol. 46 No. 12 P. 6092–6102

We study the additive theory of arbitrary ﬁgures in linear spaces, that is, the theory of addition extended to sets of vectors. Our main result is the following: if a linear space is inﬁnite, then the additive theory of ﬁgures admits interpreting second-order arithmetic and, therefore, it has such or higher degree of undecidability. For countably inﬁnite spaces, ...

Added: May 1, 2026

On the minimum number of maximal distance-k independent sets in trees

Taletskii D., / Series arXiv "math". 2026.

A vertex subset of a graph is called a \textit{distance-$k$ independent set} if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals~$n$ if $n \leq k ...

Added: May 1, 2026

On Arithmetic Mirror Symmetry for smooth Fano fourfolds

Ovcharenko M., / Series arXiv "math". 2026.

We introduce an explicit class of tempered Laurent polynomials in the sense of Villegas and Doran--Kerr in n⩽4 variables including all Landau--Ginzburg models for smooth Fano threefolds with very ample anticanonical class. We check that it contains Landau--Ginzburg models for various Fano fourfolds which are complete intersections in smooth toric varieties and Grassmannians of planes, ...

Added: April 30, 2026

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

We deal with the global in time weak solutions to the 1D compressible Navier-Stokes system of equations for large discontinuous initial data and nonhomogeneous boundary conditions of three standard types. We prove the Lipschitz-type continuous dependence of the solution $(\eta,u,\theta)$, in a norm slightly stronger than $L^{2,\infty}(Q)\times L^2(Q)\times L^2(Q)$, on the initial data $(\eta^0,u^0,e^0)$ in a ...

Added: April 18, 2026

On the dimension of the space of static potentials on three-manifolds

Medvedev V., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Added: April 3, 2026

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.

Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...

Added: April 2, 2026

Homogeneous maximizers of the Blaschke-Santalo-type functionals

Kolesnikov A., / Series arXiv "math". 2025.

We study Blaschke--Santal{ó}-type inequalities for N>=2 sets (functions) and a special class of cost functions. In particular, we prove new results about reduction of the maximization problem for the Blaschke--Santal{ó}-type functional to homogeneous case (functional inequalities on the sphere) and extend the symmetrization argument to the case of N>2 sets. We also discuss links to the ...

Added: February 13, 2026

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

Sorokin K., Beketov M., Онучин А. et al., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.

Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the ...

Added: January 15, 2026

On finding formal power-logarithmic expansions of solutions to q-difference equations

Gaianov N., Parusnikova A., / Cornell University. Серия math "arxiv.org". 2025.

An algebraic q-difference equation is considered. A sufficient condition for the existence of a formal power-logarithmic expansion of a solution to such an equation in the neighborhood of zero is proposed. An example of applying this sufficient condition for constructing a formal expansion of a solution to a certain q-difference analogue of the fifth Painlevé equation ...

Added: December 25, 2025

Ideal of the variety of flexes of plane cubics

Popov V., / Series arXiv "math". 2025. No. 2502.01539.

We prove that the variety of flexes of algebraic curves of degree 3 in the projective plane is an ideal theoretic complete intersection in the product of a two-dimensional and a nine-dimensional projective spaces. ...

Added: December 16, 2025

Random walks on rank one symmetric spaces of noncompact type

Gnetov F., Konakov V., / Series arXiv "math". 2025. No. 2512.04667.

We establish a central limit theorem, a local limit theorem, and a law of large numbers for a natural random walk on a symmetric space M of non-compact type and rank one. This class of spaces, which includes the complex and quaternionic hyperbolic spaces and the Cayley hyperbolic plane, generalizes the real hyperbolic space Hn. Our approach introduces ...

Added: December 5, 2025

Cascades of Lorenz attractors in the Shimizu-Morioka model

Kazakov A., Koryakin V., Safonov K. et al., / Series arXiv "math". 2025.

The Lorenz attractor is the first example of a robustly chaotic non-hyperbolic attractor. Each orbit of such an attractor has a positive top Lyapunov exponent, and this property persists under small perturbations despite possible bifurcations of the attractor. In this paper, we study the boundary of the Lorenz attractor existence region in the Shimizu-Morioka model. ...

Added: December 4, 2025

Асимптотический вариант метода параметрикс для цепей Маркова, сходящихся к диффузиям

Bitter I., Konakov V., / Cornell University. Серия arXiv "math". 2025. № 2505.24548.

В работе приводится обобщение локальной предельной теоремы о сходимости неоднородных цепей Маркова к диффузионному пределу на случай, когда соответ- ствующие коэффициенты процессов удовлетворяют слабым условиям регулярности и совпадают лишь асимптотически. В частности, рассматриваемые нами коэффици- енты сноса могут быть неограниченными с не более чем линейным ростом, а оценки отражают перенос терминального состояния неограниченным трендом через ...

Added: December 3, 2025