### ?

## Detecting matrices of combinatorial rank three

Journal of Combinatorial Theory, Series A. 2014. Vol. 126. P. 166-176.

Shitov Y.

The smallest integer k for which the elements of a real matrix A can be expressed as A_ij = min B_it + C_tj with B an m-by-k matrix and C an k-by-n matrix is called the combinatorial rank of A. This notion was introduced by Barvinok in 1993, and he posed a problem on the complexity of detecting matrices with combinatorial rank equal to a fixed integer k. Fast algorithms solving this problem have been known only for k=2, and we construct an algorithm that decides whether or not a given matrix has combinatorial rank three in time O((m + n)^3 mn log(mn)).

Keywords: алгоритмmatrix factorizationsalgorithmtropical semiringтропическое полукольцофакторизация матриц

Publication based on the results of:

Shitov Y., Advances in Mathematics 2014 Vol. 254 P. 138-156

The tropical arithmetic operations on R are defined by a⊕b=min{a, b} and a⊗b=a+b. Let A be a tropical matrix and k a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^{m×k} and C∈R^{k×n} satisfying B⊗C=A. We show that no algorithm for TMF is likely to work in polynomial ...

Added: January 10, 2014

Shitov Y., Linear and Multilinear Algebra 2015

We give a tropical proof of a recent result of Mohindru on the CP-rank conjecture over min-max semiring. ...

Added: April 14, 2015

Shitov Y., Proceedings of the American Mathematical Society 2014 Vol. 142 P. 15-19

We show that neither the Barvinok rank nor the Kapranov rank of a tropical matrix M can be defined in terms of the regular mixed subdivision produced by M. This answers a question asked by Develin, Santos and Sturmfels. ...

Added: October 5, 2013

Shitov Y., Journal of Mathematical Sciences 2013 Vol. 193 No. 5 P. 802-808

We consider the rank functions of matrices over semirings, functions that generalize the classical notion of the rank of a matrix over a field. We study semirings over which the factor and Gondran–Minoux ranks of any matrix coincide. It is shown that every semiring satisfying that condition is a subsemiring of a field. We provide ...

Added: January 20, 2014

Vladislav E. Kruglov, Dmitry S. Malyshev, Olga V. Pochinka, Topological classification of Ω-stable flows on surfaces by means of effectively distinguishable multigraphs / Cornell University. Series math "arxiv.org". 2017. No. 1706.01695v1.

Structurally stable (rough) flows on surfaces have only finitely many singularities and finitely many closed orbits, all of which are hyperbolic, and they have no trajectories joining saddle points. The violation of the last property leads to Ω-stable flows on surfaces, which are not structurally stable. However, in the present paper we prove that a ...

Added: September 11, 2017

Providence : American Mathematical Society, 2014

This volume contains the proceedings of the International Workshop on Tropical and Idempotent Mathematics, held at the Independent University of Moscow, Russia, from August 26-31, 2012. The main purpose of the conference was to bring together and unite researchers and specialists in various areas of tropical and idempotent mathematics and applications. This volume contains articles ...

Added: February 1, 2015

Shitov Y., Journal of Algebra 2012 Vol. 370 P. 1-4

The paper gives a complete description of the subgroups of the semigroup of tropical n-by-n matrices up to an isomorphism. ...

Added: November 7, 2012

Shitov Y., Вестник Московского университета. Серия 1: Математика. Механика 2011 № 5 С. 58-61

We present an example of a 6x6 matrix A with tropical rank equal to 4 and Kapranov rank equal to 5. This disproves the conjecture formulated by M. Chan, A. Jensen, and E. Rubei. ...

Added: January 6, 2013

Дали Ф. А., Mironkin V., Проблемы информационной безопасности. Компьютерные системы 2018 № 1 С. 113-121

Two models of the tree modes of hash functions are introduced. For each model algorithms of computing of the hash code are formulated and their numerical characteristics are obtained. In terms of the constructed models we classify some existing algorithms for parallel hashing and identify some weaknesses of corresponding primitives. ...

Added: May 28, 2018

Shitov Y., Linear Algebra and its Applications 2012 Vol. 436 No. 9 P. 3247-3253

We investigate the Kapranov rank functions of tropical matrices for different ground fields. For any infinite ground field we show that the rank-product inequality holds for Kapranov rank, and we prove that the Kapranov rank respects Green’s preorders on the semigroup of tropical n-by-n matrices. The rank-product inequality is shown to fail for Kapranov rank ...

Added: November 9, 2012

Shitov Y., Linear and Multilinear Algebra 2016 Vol. 64 No. 2 P. 219-220

We give a tropical proof of a recent result of Mohindru on the CP-rank conjecture over min-max semiring. ...

Added: December 16, 2015

Yakovlev E., Епифанов В. Ю., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2018 № 2(46) С. 47-55

The objects of research are two-dimensional compact polyhedra with an Euclidean cell decomposition, which are pseudomanifolds with boundary. The goal is to create new effective algorithms for computing the bases of absolute and relative homology groups modulo 2. Proposed a reduction procedure to a similar problem for polyhedra of lesser dimensionality, containing fewer number of cells. We ...

Added: October 4, 2018

Shitov Y., Linear Algebra and its Applications 2012 Vol. 437 No. 11 P. 2727-2732

The notion of the factor rank of tropical matrices is considered. We construct a linear-time algorithm that either finds a full-rank 3 × 3 submatrix of a given matrix A or concludes that the factor rank of A is less than 3. We show that there exist matrices of factor rank 4 whose 4 × 4 submatrices are all rank ...

Added: January 6, 2013

Sirotkin A., Труды СПИИРАН 2013 № 25 С. 204-220

The paper describe key points in algebraic bayesian network knowledge pattern implementation on C++ programming language. Knowledge pattern implemented as class that handle and store estimation for knowledge pattern elements. It also provide a couple of methods for processing knowledge pattern such as consistency update and a posteriori inference. ...

Added: March 24, 2014

Protasov V., Jungers R., Linear Algebra and its Applications 2013 Vol. 438 No. 11 P. 4448-4468

We introduce a new approach to evaluate the largest Lyapunov exponent of a family of nonnegative matrices. The method is based on using special positive homogeneous functionals on , which gives iterative lower and upper bounds for the Lyapunov exponent. They improve previously known bounds and converge to the real value. The rate of convergence ...

Added: February 23, 2016

Bliznets Ivan, Fomin F., Pilipczuk M. et al., Algorithmica 2016 Vol. 76 No. 2 P. 569-594

We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time 2^(𝜆𝑛) for some 𝜆<1. These are the first algorithms breaking the trivial 2^𝑛 poly(n) bound of the brute-force search for these problems. ...

Added: October 26, 2018

Chebotarev A., Teretenkov A. E., Applied Mathematics and Computation 2014 Vol. 234 P. 380-384

We describe a simple implementation of the Takagi factorization of symmetric matrices $A = U\Lambda U^T$ with unitary $U$ and diagonal $\Lambda$ in terms of the square root of an auxiliary unitary matrix and the singular value decomposition of $A$. The method is based on an algebraically exact expression. For parameterized family $A_\epsilon = A ...

Added: June 4, 2014

Vorobyova N. I., , in : Логистика: современные тенденции развития. Материалы XV Международной научно-практической конференции 7, 8 апреля 2016. : СПб. : ГУМРФ имени адмирала С.О. Макарова, 2016. P. 261-264.

The article contains enhanced algorithm for calculating the parameters of EOQ model that takes into account simultaneous multi-product supplies and all unit quantity discounts. ...

Added: February 20, 2018

Лакомкин Е. Д., Пузыревский И.В., Рыжова Д. А., В кн. : Доклады всероссийской научной конференции АИСТ’2013. : М. : Национальный открытый университет «ИНТУИТ», 2013. С. 184-195.

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

Added: October 1, 2014

Batagelj V., PRAPROTNIK S., Social Network Analysis and Mining 2016 Vol. 6 No. 1 P. 1-22

n a temporal network, the presence and activity of nodes and links can change through time. To describe temporal networks we introduce the notion of temporal quantities. We define the addition and multiplication of temporal quantities in a way that can be used for the definition of addition and multiplication of temporal networks. The corresponding ...

Added: November 1, 2018

Penzar D., Krivozubov M., Spirin S., BMC Bioinformatics 2018 Vol. 19 No. 374 P. 1-14

Background. Many algorithms and programs are available for phylogenetic reconstruction of families of proteins. Methods used widely at present use either a number of distance-based principles or character-based principles of maximum parsimony or maximum likelihood.
Results. We developed a novel program, named PQ, for reconstructing protein and nucleic acid phylogenies following a new character-based principle. Being ...

Added: October 26, 2018

Gnatenko A., Zakharov V., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 3 P. 303-324

The syntax and semantics of the new temporal logic LP-CTL * designed for the formal specification of the behavior of sequential responsive programs, modeled by automata-transducers (transducers) over semigroups, are developed. An algorithm is developed for verifying the feasibility of the formulas of the proposed temporal logic on models represented by finite transducers working on ...

Added: June 14, 2018

Polishchuk A., Positselski L., Transactions of the American Mathematical Society 2012 Vol. 364 No. 10 P. 5311-5368

We define and study the Hochschild (co)homology of the second kind (known also as the Borel-Moore Hochschild homology and the compactly supported Hochschild cohomology) for curved DG categories. An isomorphism between the Hochschild (co)homology of the second kind of a CDG-category B and the same of the DG category C of right CDG-modules over B, ...

Added: June 27, 2012

Trubochkina N. K., Кондратьев Н. В., Мир техники кино 2015 Т. 37 № 3 С. 6-16

A new approach in the development of three-dimensional movies without glasses, but rather, the technique of fantastic graphics and media worlds creating with the help of mathematics and computer software, as the basis for the subsequent encoding a lenticular screen, is proposed. A parametric fractals calculation model, taking into account the position of the virtual ...

Added: October 23, 2015