?
On decision trees for orthants
Information Processing Letters. 1997. Vol. 62. No. 5. P. 265–268.
M. Rabin's principle asserts that the depth of any algebraic decision tree, recognizing a closed orthant in scRn, is no less than n. Using the techniques of Newton polyhedra, we give the shortest possible proof of this fact, extending it to arbitrary collections of open or closed orthants, and apply it to trees distinguishing real polynomials having at least l real roots.
Levashev V., / Series arXiv "math". 2026. No. 2609.06010.
We prove that continuous A-bilinear pairings on the ring of Laurent series that are invariant under continuous automorphisms coincide, up to a constant, with the pairing given by the residue of a differential form over any commutative associative ring with identity. ...
Added: September 24, 2026
Pyatov P. N., Pivovarov P. A., / Series math "arxiv.org". 2026. No. 2609.06274.
We investigate a special ansats that allows for an iterative solution of the constant Yang-Baxter equation. Testing this ansatz, we construct four sequences of the constant R-matrices. In each sequence the R-matrices act on the tensor squares of vector spaces of linearly growing dimensions. Each R-matrix also depends on a single complex parameter.
By analyzing the ...
Added: September 24, 2026
Medvedev V., / Series arXiv "math". 2026.
We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...
Added: September 19, 2026
Poddiakov A., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.
Clarity of knowledge and reasoning is necessary in many cases. Yet vagueness in scientific thinking related to surprise, curiosity, "ability to engage with not-knowing" (de Freitas) and abductive reasoning is also a crucially important source of scientific creativity which supplements combinatorial logic when dealing with the already known. Starting from studies by C. S. Peirce ...
Added: September 15, 2026
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
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
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
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
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
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
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
Galitsky B., Ilvovsky D., Goncharova E., , in: Proceedings of the 10th International Workshop "What can FCA do for Artificial Intelligence?"Vol. 3233.: CEUR Workshop Proceedings, 2022. P. 75–87.
Supported decision trees that have been first proposed to boost the performance and the explainability of the expert systems built upon the texts can become a great basis for the machine reading comprehension (MRC) systems. The supported decision tree is based on building and combining the corresponding discourse trees for the text passage. In this work, ...
Added: November 1, 2022