?
The Complexity of Positive Semidefinite Matrix Factorization
SIAM Journal on Optimization. 2017. Vol. 27. No. 3. P. 1898–1909.
Shitov Y.
Let $A$ be an $m\times n$ matrix with nonnegative real entries. The PSD rank of $A$ is the smallest integer $k$ for which there exist $k\times k$ real PSD matrices $B_1,\ldots,B_m$, $C_1,\ldots,C_n$ satisfying $A(i|j)=\operatorname{tr}(B_iC_j)$ for all $i,j$. This paper determines the computational complexity status of the PSD rank. Namely, we show that the problem of computing this function is polynomial-time equivalent to the existential theory of the reals.
Shipilov F., Barnyakov A., Ivanov A. et al., / Series Physics "arxiv.org". 2026.
A fast simulation of the detector response is a vital task in high-energy physics (HEP). Traditional Monte-Carlo methods form the backbone of modern particle physics simulation software but are computationally expensive. We present a machine-learning-based approach to fast simulation of the Focusing Aerogel Ring Imaging Cherenkov (FARICH) detector response. Given a particle track and momentum, ...
Added: May 19, 2026
Dorovskiy A., / Series arXiv "math". 2026.
In this paper the structural stability of generic families of vector fields of the PC-HC class on the two-dimensional sphere is proved. A classification of these families up to moderate equivalence in neighborhoods of their large bifurcation supports is presented, based on such invariants as the configuration and the characteristic set. The realization lemma is proved. ...
Added: May 14, 2026
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
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
Derkacheva A., Sakirkina M., Kraev G. et al., /. 2026.
Comprehensive data on natural hazards and their consequences are crucial for effective for risk assessment, adaptation planning, and emergency response. However, many countries face challenges with fragmented, inconsistent, and inaccessible data, particularly regarding local-scale events. To address this data gap in Russia, we developed an end-to-end processing pipeline that scrapes news from various online sources, ...
Added: April 28, 2026
Pilé I., Deng Y., Shchur L., / Series arXiv "math". 2026. No. 2604.10254.
We investigate the spatial overlap of successive spin configurations in Markov chain Monte Carlo simulations using the local Metropolis algorithm and the Svendsen-Wang and Wolff cluster algorithms. We examine the dynamics of these algorithms for two models in different universality classes: the Ising model and the Potts model with three components. The overlap of two ...
Added: April 20, 2026
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
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
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
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
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
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
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
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
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
Смирнов И. А., Разумов П. В., Сафарьян О. А. et al., Изд-во ВлГУ, 2019.
В данной статье представлен проект модификации и оптимизации ρ – метода факторизации Полларда с помощью рекурсивного метода подсчета факторизации чисел, работающий быстрее стандартного алгоритма на 27%, что сможет значительно облегчить работу по расшифрованию и криптографическому анализу различных шифров типа RSA. Были рассмотрены и использованы алгоритм факторизации, алгоритм Эвклида для нахождения НОД, подсчитана алгоритмическая сложность, матрица ...
Added: May 11, 2023
Черкесова Л. В., Сафарьян О. А., Смирнов И. А., Молодой исследователь Дона 2018 Т. 3 (12) С. 111–121
The paper presents the project implementation of ρ-factor Pollard factorization in C ++, which works faster than the standard algorithm by 27%, which can significantly facilitate the work in deciphering and cryptanalysis of various ciphers such as RSA ...
Added: May 9, 2023
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Rybakov M., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595
We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...
Added: January 6, 2023
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2022 Vol. 16 P. 276–291
The edge-coloring problem is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. The complexity status of this problem is known for all the classes defined by the sets of forbidden subgraphs with 7 edges each. In this paper, we ...
Added: December 31, 2022
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
A hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then the class is said to be finitely defined. The concept of a boundary class is a useful tool for the analysis ...
Added: December 6, 2022
Kochergin V., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113–119
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 ...
Added: October 29, 2022
Rybakov M., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60
We prove that branching-time temporal logics CTL and CTL* are polynomial-time embeddable into their single-variable fragments. It follows that satisfiability for CTL and CTL*, and therefore also for alternating-time temporal logics ATL and ATL*, in languages with one propositional variable is as algorithmically hard as satisfiability for the full logic: EXPTIME-complete for CTL and ATL, and 2EXPTIME-complete for CTL* and ATL*. We discuss applicability of the technique used in the proofs to other ...
Added: May 12, 2022
Faliszewski P., Karpov A., Obraztsova S., Autonomous Agents and Multi-Agent Systems 2022 Vol. 36 Article 18
We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height. We also show a polynomial-time algorithm for sampling group-separable elections uniformly at ...
Added: March 14, 2022
Malyshev D. S., Приставченко О. В., Optimization Letters 2022 Vol. 16 P. 1403–1409
The vertex 3-colourability problem is to decide whether the vertex set of a given graph
can be split into three subsets of pairwise non-adjacent vertices. This problem is known
to be NP-complete in a certain class of graphs, defined by an explicit description of
allowed 5-vertex induced subgraphs in them. In the present paper, we improve this
result by ...
Added: February 25, 2022