?
Euclidean Distance Matrices and Separations in Communication Complexity Theory
Discrete and Computational Geometry. 2019. Vol. 61. No. 3. P. 653–660.
Shitov Y.
A Euclidean distance matrix D(α) is defined by D_ij=(α_i−α_j)^2, where α=(α_1,…,α_n) is a real vector. We prove that D(α) cannot be written as a sum of [2sqrt(n)−2] nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation.
Glutsyuk A., / Series arXiv "math". 2026.
B.Josephson (Nobel Prize, 1973) predicted a tunnelling effect for a system of two superconductors separated by a narrow dielectric (such a system is called Josephson junction): existence of a supercurrent through it and equations governing it. The overdamped Josephson junction is modeled by the family of differential equations on the 2-torus, dθdτ=1ω(cosθ+B+Acosτ), which is known as ...
Added: September 8, 2026
Pochinka O., Shmukler V., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Anosov flows have a long and rich history, firstly motivated by the
study of geodesic flows in negative curvature surface by Anosov and Sinai.
Not every closed manifold admits an Anosov flow for well-known reasons:
the fundamental group of a 3-manifold M admitting an Anosov flow must
have exponential growth, and M must be universally covered by R3. Nevertheless,
there ...
Added: August 31, 2026
Shabanov N., Kuricheva O., Kurbatova J. et al., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
The carbon balance of an ecosystem is the difference between Gross Primary Productivity (GPP) and Ecosystem Respiration (Reco) as expressed by Net Ecosystem Exchange (NEE). While remote sensing retrievals of GPP have reached maturity, Reco estimation remains underexplored and ultimately cast bias on NEE. Here we present an end-to-end multi-scale analysis of the mechanism of ...
Added: August 21, 2026
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Loubenets E. R., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
In many quantum applications it is important to know whether or not a Bell nonlocal two-qudit state exhibits its nonlocality under correlation scenarios with some given numbers S1,S2≥1 of generalized quantum measurements at two sites. In the present article, we find analytically a new general locality condition sufficient for a nonseparable Werner state with a ...
Added: July 21, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity.
To prove this, we study ...
Added: July 16, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...
Added: July 16, 2026
Panov V., Ryabchenko A., / Series arXiv "stat.ME". 2026. No. 2607.05048.
This paper investigates the problem of statistical inference for a mixture distribution consisting of a discrete and a continuous component, with a particular focus on the class of rational-infinitely divisible distributions. We consider non-parametric estimation of both components of the mixture as well as the quasi-L{é}vy measure, assuming that the mixture belongs to the class ...
Added: July 9, 2026
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 2026
Konakov V., Kucher D., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
In this paper, we construct strong approximations for discrete-time Markov chains weakly converging to continuous diffusion processes, as well as for their perturbed counterparts. Under the assumption of bounded coefficients, we construct closely coupled versions of these processes on a shared probability space. In particular, for both non-degenerate and degenerate cases, we maximize the probability ...
Added: June 11, 2026
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
Vereshchagin N., Дектярев М. В., Математический сборник 2025 Т. 216 № 6 С. 3–45
Полудуплексная коммуникационная сложность с противником определена в работе [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В ...
Added: August 23, 2025
Ignatiev A., Mihajlin I., Smal A., , in: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248.: Saarbrücken, Вадерн: Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.
Added: November 9, 2023
Vyalyi M., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160
We consider a generalization of the Pólya–Kasteleyn approach to counting the number of perfect matchings in a graph based on computing the symbolic Pfaffian of a directed adjacency matrix of the graph. Complexity of algorithms based on this approach is related to the complexity of the sign function of a perfect matching in generalized decision ...
Added: August 20, 2021
Podolskii V. V., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26
A major goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems f:({0, 1}^n)^k → {0, 1} with k > log n parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every k ≥ log n, showing in both cases that Θ(1 + ⌈log n⌉/ log ⌈1 + k/ log n⌉) bits are necessary and ...
Added: December 23, 2020
Shitov Y., Fuzzy Sets and Systems 2020 Vol. 382 P. 165–171
Matrix factorization problems over various semirings naturally arise in different contexts of modern pure and applied mathematics. These problems are very hard in general and cause computational difficulties in applications. We give a survey of what is known on the algorithmic complexity of Boolean, tropical, nonnegative, and positive semidefinite factorizations, and we examine the behavior ...
Added: November 11, 2020
Klenin E., Kozachinskiy A., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–15.
Added: August 28, 2018
Shitov Y., SIAM Review 2017 Vol. 59 No. 4 P. 794–800
Using elementary linear algebra, we develop a technique that leads to solutions of two widely known problems on nonnegative matrices. First, we give a short proof of the result by Vavasis stating that the nonnegative rank of a matrix is NP-hard to compute. This proof is essentially contained in the paper by Jiang and Ravikumar, ...
Added: November 9, 2017
Kozachinskiy A., Theory of Computing Systems 2018 Vol. 62 No. 3 P. 583–599
In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability ε). Instead of one-way transmission we allow them to interact. They may also ...
Added: February 9, 2017
Kozachinskiy A., , in: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, ProceedingsVol. 9691: Lecture Notes in Computer Science.: Switzerland: Springer, 2016. P. 207–222.
In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability εε). Instead of one-way transmission we ...
Added: September 16, 2016
Brody J., Buhrman H., Koucký M. et al., Algorithmica 2016 Vol. 76 No. 3 P. 749–781
Newman's theorem states that we can take any public-coin
communication protocol and convert it into one that uses only
private randomness with only a little increase in communication
complexity. We consider a reversed scenario in the context of
information complexity: can we take a protocol that uses private
randomness and convert it into one that ...
Added: March 2, 2016
Kozachinskiy A., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 296–309.
Added: February 29, 2016