Sergey’s main research activity has been in the area of tropical linear algebra and tropical convexity. These are the linear algebra and convex geometry developed over the max-plus semiring: the set of real numbers with adjoined negative infinity element, equipped with the addition “a+ b”:= max(a, b) and the multiplication “ab” = a + b. These areas can be viewed in a more general framework of idempotent/tropical mathematics, which has applications in such diverse areas as algebraic geometry, discrete event systems, scheduling, optimal control and Hamilton-Jacobi PDE’s, string comparison algorithms, static analysis of computer programs.
His main achievements in tropical linear algebra and tropical convexity can be briefly described as follows. Citations refer to the list of selected papers given below.
- In collaboration with P. Butkovic and H. Schneider, Sergey generalized the cyclicity theorem on tropical matrix powers to the reducible case in the form of CSR expansions and described attraction cones (sets of vectors converging to an eigenvector) as solution sets of tropical linear systems of equations [6,7,10]. In the same collaboration they developed the tropical analogue of the theory of Z-matrix equations (of the form x=Ax+b)[11], commuting matrices (with R.D. Katz [8] ) and the core of nonnegative matrix [14]. With G.Merlet and T. Nowak, Sergey applied the CSR expansion idea to obtain new more efficient bounds on the periodicity of tropical matrix powers [18,19].
- In collaboration with S. Gaubert [3] Sergey introduced the max-plus analogue of cyclic projections method, obtaining separation theorem for several max-plus convex sets, and deducing the max-plus analogue of Helly’s theorem. Using equivalence between tropical polyhedra and mean-payoff games, the group proposed the first known method for computing the whole spectrum of tropical two-matrix eigenproblem[13], and worked (with R.D. Katz) on new algorithms of tropical linear programming and their possible application to static analysis of computer programs [9]. A number of results on tropical convexity were also obtained in an individual paper [5] and in collaboration with V. Nitica [16,17]. Notably, they also developed an analogue of tropical convexity over max-min semiring. Based on the same geometric intuition, Sergey also described eigenvectors in max-min and max-Lukasiewicz linear algebra, in joint works with M. Gavalec and Z. Nemcova [23, 30]
- The main outcomes of the EPSRC grant “Tropical Optimisation” are: 1) the development of a new tropical implementation of the AHP decision method (joint work with N. Krivulin [28]), 2) solution of some problems of tropical bi-level optimisation (joint work with Z. Liu [27]), 3) new bounds on the rank-one transient of tropical inhomogeneous matrix products in a special case (with A. Kennedy-Cochran-Patrick and S. Berezny [26]), 4) application of tropical Jacobi identity to analysing optimal assignments with supervisions (joint with A. Niv and M. Maccaig [29])
Apart from the tropical linearity, his interests also include nonlinear optimisation, combinatorial games, nonnegative matrices, theory of partially ordered sets, linear algebra over fuzzy semirings, abstract convexity, Perron-Frobenius theory and diagonal similarity matrix scaling.
Currently, Sergey has two PhD students: Arthur Kennedy-Cochran-Patrick and Any Muanalifah. Both of them started in 2017.
Arthur’s work is focused on tropical non-homogeneous matrix products [P1] and transients of periodicity of tropical matrix powers [P2]. Particularly, preprint [P1] is generalising the approach and the results of [26]. In this preprint, new CSR decompositions of inhomogeneous matrix products are defined and new bounds on the factor rank transient of such products are obtained, in an important special case.
Any has been working on applications of tropical algebra in cryptography. In particular, new modifications of the tropical version of Stickel’s protocol have been suggested and some attacks on them have been described in [P3] (accepted for publication in Applications of Mathematics). The ongoing work is concerned with developing some new attacks on the protocols proposed in the works of Grigoriev and Shpilrain.
Recent supervision of MSci students also resulted in new research: see in particular [P4] based on the MSci project of J. Parsons (supervised in 2018-19) and developed during the visit of H. Wang in 2020. This work is developing the application of mean-payoff game solvers to tropical pseudolinear and tropical pseudoquadratic optimisation.