Sergei Sergeev
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sergei Sergeev has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Hans Schneider
University of Wisconsin-Madison USA
5 shared publications - Ján Plavka
Tech Univ, Dept Math & Theoret Informat, Nemcovej 32, Kosice 04200, Slovakia
5 shared publications - Viorel Nitica
Department of Mathematics, West Chester University of Pennsylvania, West Chester, PA 19383, USA
5 shared publications - Oliver Mason
Maynooth University
4 shared publications - Buket Benek Gursoy
Hamilton Institute, National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland
3 shared publications - Martin Gavalec
Univ Hradec Kralove, Fac Informat & Management, Rokitanskeho 62, Hradec Kralove 50003, Czech Republic
3 shared publications
Latest Publications
- Open Access
On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: "Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$." We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.Open AccessOn the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: "Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$." We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments. - 20 September 2021
- Published by Taylor & Francis in Communications in Algebra
- Vol. 50 (2) , 861-879
On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that for a unique t and matrices A, V, F of appropriate dimensions, find this t.” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.- 20 September 2021
- Published by Taylor & Francis in Communications in Algebra
- Vol. 50 (2) , 861-879
On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that for a unique t and matrices A, V, F of appropriate dimensions, find this t.” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.- 3 February 2021
- Published by Taylor & Francis in Linear and Multilinear Algebra
- Vol. 70 (19) , 4320-4350
On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by , where is the weak CSR threshold and is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for and , naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on , which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.- 3 February 2021
- Published by Taylor & Francis in Linear and Multilinear Algebra
- Vol. 70 (19) , 4320-4350
On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by , where is the weak CSR threshold and is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for and , naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on , which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.- Open Access
(K,L)-eigenvectors in max-min algebra
Using the concept of (K,L)-eigenvector, we investigate the structure of the max-min eigenspace associated with a given eigenvalue of a matrix in the max-min algebra (also known as fuzzy algebra). In our approach, the max-min eigenspace is split into several regions according to the order relations between the eigenvalue and the components of x. The resulting theory of (K,L)-eigenvectors, being based on the fundamental results of Gondran and Minoux, allows to describe the whole max-min eigenspace explicitly and in more detail.
Open Access(K,L)-eigenvectors in max-min algebra
Using the concept of (K,L)-eigenvector, we investigate the structure of the max-min eigenspace associated with a given eigenvalue of a matrix in the max-min algebra (also known as fuzzy algebra). In our approach, the max-min eigenspace is split into several regions according to the order relations between the eigenvalue and the components of x. The resulting theory of (K,L)-eigenvectors, being based on the fundamental results of Gondran and Minoux, allows to describe the whole max-min eigenspace explicitly and in more detail.
- Open Access
On the Tightness of Bounds for Transients of Weak CSR Expansions and Periodicity Transients of Critical Rows and Columns of Tropical Matrix Powers
We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by $\max\{T_1,T_2\}$, where $T_1$ is the weak CSR threshold and $T_2$ is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for $T_1$ and $T_2$, naturally leading to the question which matrices, if any, attain these bounds. In the present paper we characterize the matrices attaining two particular bounds on $T_1$, which are generalizations of the bounds of Wielandt and Dulmage-Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.Open AccessOn the Tightness of Bounds for Transients of Weak CSR Expansions and Periodicity Transients of Critical Rows and Columns of Tropical Matrix Powers
We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by $\max\{T_1,T_2\}$, where $T_1$ is the weak CSR threshold and $T_2$ is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for $T_1$ and $T_2$, naturally leading to the question which matrices, if any, attain these bounds. In the present paper we characterize the matrices attaining two particular bounds on $T_1$, which are generalizations of the bounds of Wielandt and Dulmage-Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case. - Open Access
Tropical analogues of a Dempe-Franke bilevel optimization problem
We consider the tropical analogues of a particular bilevel optimization problem studied by Dempe and Franke and suggest some methods of solving these new tropical bilevel optimization problems. In particular, it is found that the algorithm developed by Dempe and Franke can be formulated and its validity can be proved in a more general setting, which includes the tropical bilevel optimization problems in question. We also show how the feasible set can be decomposed into a finite number of tropical polyhedra, to which the tropical linear programming solvers can be applied.
Open AccessTropical analogues of a Dempe-Franke bilevel optimization problem
We consider the tropical analogues of a particular bilevel optimization problem studied by Dempe and Franke and suggest some methods of solving these new tropical bilevel optimization problems. In particular, it is found that the algorithm developed by Dempe and Franke can be formulated and its validity can be proved in a more general setting, which includes the tropical bilevel optimization problems in question. We also show how the feasible set can be decomposed into a finite number of tropical polyhedra, to which the tropical linear programming solvers can be applied.
- 1 August 2018
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 550, 59-86
Reachability of eigenspaces for interval circulant matrices in max-algebra
- 1 August 2018
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 550, 59-86
Reachability of eigenspaces for interval circulant matrices in max-algebra
- Open Access
Reachability of eigenspaces for interval circulant matrices in max-algebra
A nonnegative matrix A is said to be strongly robust if its max-algebraic eigencone is universally reachable, i.e., if the orbit of any initial vector ends up with a max-algebraic eigenvector of A. Consider the case when the initial vector is restricted to an interval and A can be any matrix from a given interval of nonnegative circulant matrices. The main aim of this paper is to classify and characterize the six types of interval robustness in this situation. This naturally leads us also to study the max-algebraic spectral theory of circulant matrices and the relation of inclusion between attraction cones of circulant matrices in max-algebra.
Open AccessReachability of eigenspaces for interval circulant matrices in max-algebra
A nonnegative matrix A is said to be strongly robust if its max-algebraic eigencone is universally reachable, i.e., if the orbit of any initial vector ends up with a max-algebraic eigenvector of A. Consider the case when the initial vector is restricted to an interval and A can be any matrix from a given interval of nonnegative circulant matrices. The main aim of this paper is to classify and characterize the six types of interval robustness in this situation. This naturally leads us also to study the max-algebraic spectral theory of circulant matrices and the relation of inclusion between attraction cones of circulant matrices in max-algebra.
- Open Access
Tropical convexity over max-min semiring
This is a survey on an analogue of tropical convexity developed over the max-min semiring, starting with the descriptions of max-min segments, semispaces, hyperplanes and an account of separation and non-separation results based on semispaces. There are some new results. In particular, we give new "colorful" extensions of the max-min Caratheodory theorem. In the end of the paper, we list some consequences of the topological Radon and Tverberg theorems (like Helly and Centerpoint theorems), valid over a more general class of max-T semirings, where multiplication is a triangular norm.
Open AccessTropical convexity over max-min semiring
This is a survey on an analogue of tropical convexity developed over the max-min semiring, starting with the descriptions of max-min segments, semispaces, hyperplanes and an account of separation and non-separation results based on semispaces. There are some new results. In particular, we give new "colorful" extensions of the max-min Caratheodory theorem. In the end of the paper, we list some consequences of the topological Radon and Tverberg theorems (like Helly and Centerpoint theorems), valid over a more general class of max-T semirings, where multiplication is a triangular norm.
- 22 September 2016
- Published by Institute of Information Theory and Automation in Kybernetika
- Vol. 52 (4) , 497-513
Characterizing matrices with $\bf{X}$-simple image eigenspace in max-min semiring
- 22 September 2016
- Published by Institute of Information Theory and Automation in Kybernetika
- Vol. 52 (4) , 497-513
Characterizing matrices with $\bf{X}$-simple image eigenspace in max-min semiring