• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Эффективный поиск минимального дерева на точках пространства в $l_1$-норме
  • 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
October 1, 2026
HSE Researchers Show How Congenital Motor Disorders Affect Brain Development
Researchers from HSE University’s Institute for Cognitive Neuroscience have synthesised the findings of their previous studies on brain development in children with obstetric brachial plexus palsy and arthrogryposis. Their analysis shows that impaired motor function in early childhood not only limits children’s motor experience but also affects memory, categorical thinking, and information processing. The study has been published in Frontiers in Psychology.
October 1, 2026
Window into the Body: Scientists Develop Neural Network to Detect Risk of 15 Diseases from Retinal Images
Russian universities, with the participation of HSE University, Sber, and Z-union, have developed a neural network that can simultaneously assess the risk of 15 types of pathology from retinal photographs, including not only eye diseases but also cardiovascular conditions. The AI system can help clinicians detect potentially concerning changes at an early stage, identify signs reflecting the condition of retinal blood vessels, and determine whether a patient may need further examination. The paper has been published in Frontiers in Medicine.
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.

 

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

?

Эффективный поиск минимального дерева на точках пространства в $l_1$-норме

Математические заметки. 2025. Т. 117. № 5. С. 672–679.
Kaimakov K., Malyshev D.
Research target: Computer Science Mathematics
Language: Russian
Full text
DOI
Text on another site
Keywords: эффективный алгоритмefficient algorithmcomputational geometryвычислительная геометриязадача о минимальном остовном деревеminimum spanning tree problem
Similar publications
Markovian reduction and exponential mixing in total variation for random dynamical systems
Kuksin S., Shirikyan A., Journal of Dynamics and Differential Equations 2026 P. 1098–1100
The paper deals with the problem of large-time behaviour of trajectories for discrete-time dynamical systems driven by a random noise. Assuming that the phase space is finite-dimensional and compact, and the noise is a Markov process with a transition probability satisfying some regularity hypotheses, we prove that all the trajectories converge to a unique measure ...
Added: October 1, 2026
Bounds on the derivatives of the log-cumulative distribution function of the multivariate normal distribution
Potanin B., Dolgikh S., Statistics and Probability Letters 2026 Article 110984
We derive bounds on the gradient and Hessian of the log-CDF, ln F(x), of the multivariate normal distribution. These bounds scale linearly and quadratically in ‖x‖ , respectively, with constants depending only on the covariance matrix. We demonstrate the usefulness of these bounds by proving asymptotic normality of the maximum-likelihood estimator of the multivariate probit ...
Added: October 1, 2026
Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2026)
International Joint Conferences on Artificial Intelligence, 2026.
Added: October 1, 2026
Asymptotics of Spectrum and Quantum Averages of the Hydrogen Atom in a Magnetic Field Near the Upper Boundaries of Spectral Clusters
A. V. Pereskokov, Journal of Mathematical Sciences 2026 Vol. 302 No. 4 P. 531–545
We consider the Zeeman effect problem for the hydrogen atom in a magnetic field using irreducible representations of the Karasev–Novikova algebra with quadratic commutation relations. We find the asymptotics of a series of eigenvalues and the corresponding asymptotic eigenfunctions near the upper boundaries of spectral clusters. ...
Added: October 1, 2026
Ensemble-based Prototype-Augmented Multimodal Fusion for Ambivalence/Hesitancy Recognition
Ryumina E., Aksenov A., Сысоев Д. С. et al., IEEE Computer Society, 2026.
Ambivalence/hesitancy recognition in unconstrained videos is a challenging problem due to the subtle, multimodal, and context-dependent nature of this behavioral state. In this paper, a multimodal approach for video-level ambivalence/hesitancy recognition is presented for the 10th ABAW Competition. The proposed approach integrates four complementary modalities: scene, face, audio, and text. Scene dynamics are captured with ...
Added: September 30, 2026
Simultaneous approximation of the score function and its derivatives by deep neural networks
Yakovlev K., Puchkin N., Journal of Complexity 2026 Vol. 97
We present a theory for simultaneous approximation of the score function and its derivatives, enabling the handling of data distributions with low-dimensional structure and unbounded support. Our approximation error bounds match those in the literature while relying on assumptions that relax the usual bounded support requirement. Crucially, our bounds are free from the curse of ...
Added: September 30, 2026
Conservative Entropy and Energy Correct Difference Methods for One-Dimensional Quasi-Gasdynamic Systems of Equations
Zlotnik A., Mathematical notes 2026 Vol. 120 No. 6 P. 1005–1009
Numerical methods for solving systems of gas dynamic equations are the subject of a vast literature. A special family of spatially symmetric conservative difference methods based on preliminary kinetic, or quasi-gasdynamic (QGD), regularization of these equations was constructed and successfully tested. A pressing issue is the construction of numerical methods that are not only conservative ...
Added: September 30, 2026
О числе Пикара и размерности алгебраических однородных пространств
Beldiev I., Тимашёв Д. А., Алгебра и анализ 2026 Т. 38 № 5 С. 1–10
An algebraic variety X is called a homogeneous space if there exists a transitive regular action of an algebraic group on X. We prove inequalities between the dimension of a homogeneous space of a linear algebraic group and its Picard number. ...
Added: September 30, 2026
Decoding Algorithms for Binary U-UV Codes: A Unified Survey of Performance and Complexity
Ivanov F., Kotov F., IEEE Access 2026 Vol. 14 P. 104662–104679
U-UV codes, based on the Plotkin (U, U + V) construction, provide a unified framework that includes polar and Reed–Muller codes and enables flexible design through the choice of component codes. While modern capacity-approaching codes achieve excellent performance at large block lengths, their efficiency at short and moderate lengths remains limited, especially under low-latency constraints. ...
Added: September 30, 2026
An archaic reference-free method to jointly infer Neanderthal and Denisovan introgressed segments in modern human genomes,
Planche L., Ilina A., Jay F. et al., Molecular Biology and Evolution 2026 Article 235
Admixture between populations is a common feature of human history. Admixture events introduce new genetic variation that can fuel evolution. Characterizing the significance of admixture events on the evolution of populations across various species is of great interest to evolutionary geneticists. Local Ancestry Inference (LAI) methods infer genetic ancestry of an individual at a particular ...
Added: September 30, 2026
Uniqueness theorem for completely non-degenerate B-groups
Glutsyuk A., Ilyashenko Y., Izvestiya. Mathematics 2026 Vol. 90 No. 1 P. 73–89
We show that a completely non-degenerate B-group is uniquely determined by its factor: two such groups with conformally equivalent factors are Möbius conjugate. A similar property is inherent to the quasi-Fuchsian groups but not to degenerate B-groups. We also study the factor of a B-group as a triple: the main factor, the marked characteristic complex, and a homotopy class of ...
Added: September 30, 2026
The EG-TD3 Machine Learning Architecture: Evolutionary-Guided Twin Delayed Deep Deterministic Policy Gradient
Djambong Tenkeu H., Institute for System Programming of the RAS, 2026.
Added: September 29, 2026
Серия инвариантных характеристик реальных сетей
Tuzhilin M., Автоматика и телемеханика 2026 № 11 С. 84–97
Предлагается обобщение двух известных инвариантов реальных сетей: степени и кси-центральности. Строится серия центральностей, основанная на матрице Лапласа сети и параметризованная параметром j со следующими свойствами: во-первых, при j = 0, 1 эти центральности совпадают со степенью и ксицентральностью; во-вторых, их распределение хорошо приближается распределением Вейбулла; в-третьих, для реальных сетей они имеют правостороннюю асимметрию, а для ...
Added: September 29, 2026
Нетривиальное поведение пирамидальных уединенных волн в обобщенном уравнении Гарднера
Melnikov I., Pelinovsky E., Доклады Российской академии наук. Физика, технические науки (ранее - Доклады Академии Наук. Физика) 2026 Т. 529 С. 29–36
Conditions for the emergence of pyramidal solitary waves (solitary waves possessing more than two inflection points) are presented for a family of generalized Korteweg – de Vries (KdV) equations. For the generalized Gardner equation, it is shown that pyramidal solitons are unstable. The decay of initial perturbations close to pyramidal solitary waves is demonstrated numerically. ...
Added: September 29, 2026
Pre-Calabi-Yau algebras and oriented gravity properad
Merkulov S., Journal of Pure and Applied Algebra 2026 Vol. 230 P. 1–19
We study the dual cyclic Hochschild  complex $Cyc(A,\K)$ of a (possibly, infinite-dimensional) $A_\infty$-algebra $(A,\mu)$ and prove that any pre-Calabi-Yau extension  $\pi$ of the given $A_\infty$ structure $\mu$ in $A$ induces on the cyclic cohomology of $(A,\mu)$ a representation of a new dg properad of {\em oriented}\, ribbon graphs. We compute the cohomology of that properad in terms of ...
Added: September 29, 2026
Нижние множества и свойства замкнутости классов функций подсчета
Ivanashev Y., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2026 Т. 529 С. 93–101
Язык L является нижним для релятивизируемого сложностного класса C, если CL=C. Для классов #P, GapP и SpanP известны точные нижние классы языков: Low(#P) = UP ∩ coUP, Low(GapP) = SPP и Low(SpanP) = NP ∩ coNP. В этой статье мы доказываем, что Low(TotP) = P, и приводим характеризации нижних классов функций для #P, GapP, TotP ...
Added: September 28, 2026
Combinatorics on finite words and the length of a finite-dimensional associative algebra
Хрыстик М. А., European Journal of Combinatorics 2026 Vol. 136 P. 104393–104393
Let 𝑓𝑊⁡(𝑛) be the number of different factors of length 𝑛 appearing in a word 𝑊. In a classical result by Morse and Hedlund, a characterization is given for infinite words satisfying the condition 𝑓𝑊⁡(𝑛)≤𝑛 for some 𝑛∈ℕ. In this paper, we describe the form of finite words that satisfy the condition 𝑓𝑊⁡(𝑛)≤𝑛. We study ...
Added: September 28, 2026
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
An efficient algorithm for the eigenvalue problem of a Hermitian quaternion matrix in quantum chemistry
Guo Z., Jiang T., Wang G. et al., Journal of Computational and Applied Mathematics 2025 Vol. 463
The introduction of quaternions in the quantum chemistry framework provides new ideas for solving some of the difficulties encountered in traditional approaches and is expected to expand the scope of quantum chemistry research. This paper investigates the eigenvalue problem of a Hermitian quaternion matrix by means of the complex representation of a quaternion matrix. This ...
Added: December 16, 2024
Efficient online sensitivity analysis for the injective bottleneck path problem
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2025 Vol. 19 P. 1441–1454
The tolerance of an element of a combinatorial optimization problem with respect to a given optimal solution is the maximum change, i.e., decrease or increase, of its cost, such that this solution remains optimal. The bottleneck path problem, for given an edge-capacitated graph, a source, and a target, is to find the max-min value of ...
Added: November 5, 2024
Приближенный поиск k-ого порядкового расстояния в системе точек единичного квадрата
Kaimakov K., Malyshev D., Математические заметки 2024 Т. 116 № 4 С. 504–509
Для заданных $P=(p_1,\ldots,p_n)$ --- набора точек единичного квадрата и числа $1\leq k\leq \binom{n}{2}$ в данной работе рассматривается задача поиска $k$-ого порядкового расстояния между элементами $P$ в $l_s$-норме, где $s\in \{1,\infty\}$. Иными словами, рассматривается задача поиска такого минимального $d_k$, что выполнено $\sum\limits_{i<j}\indicator(\|p_i,p_j\|_{s} \leq d_k)\geq k$, где $\indicator$ --- индикаторная функция и $s\in \{1,\infty\}$. В настоящей работе ...
Added: May 31, 2024
Многомерные калейдоскопы: геометрия, алгебра и комбинаторика
Мещеряков М. В., Математика в высшем образовании 2022 № 20 С. 53–68
Статья содержит наглядное изложение элементов теории групп, порождённых отражениями в конечномерных евклидовых пространствах, основанное на естественнонаучном понятии калейдоскопа. Она предназначена преподавателям линейной алгебры и геометрии, дискретной математики, учителям специализированных физико-математических классов школ и студентам факультетов математики и информатики различных направлений подготовки, включая ряд физических и инженерных специальностей. Через рассмотрение калейдоскопов отмечаются взаимосвязи между несколькими различными ...
Added: October 12, 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