Yaroslav Shitov
Research Subjects
Research Interests
Yaroslav Shitov has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Alexander E. Guterman
Lomonosov Moscow State University, Moscow, Russia
1 shared publication - Nicolas Gillis
Department of Mathematics and Operational Research University of Mons Rue de Houdain 9 7000 Mons Belgium
1 shared publication
Latest Publications
- 3 September 2026
- Published by Springer Nature in Annales Henri Poincare
- p. 1-18
Growth in Matrix Algebras and a Conjecture of Pérez-García, Verstraete, Wolf and Cirac
- 3 September 2026
- Published by Springer Nature in Annales Henri Poincare
- p. 1-18
Growth in Matrix Algebras and a Conjecture of Pérez-García, Verstraete, Wolf and Cirac
- 19 May 2026
- Published by Cambridge University Press (CUP) in Bulletin of the Australian Mathematical Society
- Vol. 114 (2) , 1-5
SEVERAL QUESTIONS OF LONGSTAFF ON GENERATION IN MATRIX ALGEBRAS
We solve three problems raised in recent articles by Longstaff [ Bull. Aust. Math. Soc. 102 (2020), 226–236; 103 (2021), 260–270; 104 (2021), 78–93]. We show that: (1) the length of an irreducible family of $n\times n$ rank-one matrices can take any value $1,2,\ldots ,n$ ; (2) the slot length of an irreducible pair of $n\times n$ matrices can exceed $2n-4$ ; and (3) we give bounds on the $1$ -minimum spanning lengths of irreducible pairs.- 19 May 2026
- Published by Cambridge University Press (CUP) in Bulletin of the Australian Mathematical Society
- Vol. 114 (2) , 1-5
SEVERAL QUESTIONS OF LONGSTAFF ON GENERATION IN MATRIX ALGEBRAS
We solve three problems raised in recent articles by Longstaff [ Bull. Aust. Math. Soc. 102 (2020), 226–236; 103 (2021), 260–270; 104 (2021), 78–93]. We show that: (1) the length of an irreducible family of $n\times n$ rank-one matrices can take any value $1,2,\ldots ,n$ ; (2) the slot length of an irreducible pair of $n\times n$ matrices can exceed $2n-4$ ; and (3) we give bounds on the $1$ -minimum spanning lengths of irreducible pairs.- Open Access
- 21 September 2025
- Published by Mathematical Sciences Publishers in Pacific Journal of Mathematics
- Vol. 339 (2) , 333-343
Graph thinness: a lower bound and complexity
The thinness of a simple graph G = (V, E) is the smallest integer k for which there exist a total order (V, <) and a partition of V into k classes (V 1 ,. .. , V k) such that, for all u, v, w ∈ V with u < v < w, if u, v belong to the same class and {u, w} ∈ E, then {v, w} ∈ E. We prove: • There are n-vertex graphs of thinness n-o(n), which answers a question of Bonomo-Braberman, Gonzalez, Oliveira, Sampaio, and Szwarcfiter. • The computation of thinness is NP-hard, which is a solution to a longstanding open problem posed by Mannino and Oriolo. • a total ordering < of the vertex set V and MSC2020: 05C85, 68Q17.
- 21 September 2025
- Published by Mathematical Sciences Publishers in Pacific Journal of Mathematics
- Vol. 339 (2) , 333-343
Open AccessGraph thinness: a lower bound and complexity
The thinness of a simple graph G = (V, E) is the smallest integer k for which there exist a total order (V, <) and a partition of V into k classes (V 1 ,. .. , V k) such that, for all u, v, w ∈ V with u < v < w, if u, v belong to the same class and {u, w} ∈ E, then {v, w} ∈ E. We prove: • There are n-vertex graphs of thinness n-o(n), which answers a question of Bonomo-Braberman, Gonzalez, Oliveira, Sampaio, and Szwarcfiter. • The computation of thinness is NP-hard, which is a solution to a longstanding open problem posed by Mannino and Oriolo. • a total ordering < of the vertex set V and MSC2020: 05C85, 68Q17.
- Open Access
- 23 January 2025
- Published by Mathematical Sciences Publishers in Pacific Journal of Mathematics
- Vol. 334 (1) , 143-151
Several remarks on tensor rank computation
The Waring rank of a homogeneous polynomial f is the smallest number wr f for which f is the sum of wr f powers of linear forms. We show wr(f • g) ⩽ (wr f) • (wr g) • max{deg f, deg g} if wr f > 1, wr g > 1 and answer a question of Teitler. We also discuss further questions of Koiran and Schaefer regarding the algorithmic computation of tensor ranks.
- 23 January 2025
- Published by Mathematical Sciences Publishers in Pacific Journal of Mathematics
- Vol. 334 (1) , 143-151
Open AccessSeveral remarks on tensor rank computation
The Waring rank of a homogeneous polynomial f is the smallest number wr f for which f is the sum of wr f powers of linear forms. We show wr(f • g) ⩽ (wr f) • (wr g) • max{deg f, deg g} if wr f > 1, wr g > 1 and answer a question of Teitler. We also discuss further questions of Koiran and Schaefer regarding the algorithmic computation of tensor ranks.
- 1 October 2024
- Published by Pleiades Publishing Ltd in Mathematical Notes
- Vol. 116 (3-4) , 867-868
A Refutation of the “Symmetric Substitution Conjecture”
- 1 October 2024
- Published by Pleiades Publishing Ltd in Mathematical Notes
- Vol. 116 (3-4) , 867-868
A Refutation of the “Symmetric Substitution Conjecture”
- 30 September 2024
- Published by Mathematical Sciences Publishers in Tunisian Journal of Mathematics
- Vol. 6 (3) , 543-548
Triangular ranks do not bound minimum ranks in matrix completion
- 30 September 2024
- Published by Mathematical Sciences Publishers in Tunisian Journal of Mathematics
- Vol. 6 (3) , 543-548
Triangular ranks do not bound minimum ranks in matrix completion
- 22 June 2023
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 24 (4) , 1-24
Further $\exists {\mathbb {R}}$-Complete Problems with PSD Matrix Factorizations- 22 June 2023
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 24 (4) , 1-24
Further $\exists {\mathbb {R}}$-Complete Problems with PSD Matrix Factorizations- Open Access
- 1 January 2023
- Published by International Press of Boston in Arkiv för Matematik
- Vol. 61 (1) , 203-210
On local colorings of split graphs
A semi-matching coloring of a finite simple graph G=( V, E) is a mapping phi from V to {1,..., k} such that (i) every color class is an independent set, and (ii) the edge set of the graph induced by the union of any two consecutive color classes is a matching. A semi-matching coloring. is a local coloring if, in addition, (iii) the union of any three consecutive color classes induces a triangle-free subgraph of G. In this paper, we give two counterexamples and one positive solution to three problems arisen in recent papers of You, Cao, Wang. In particular, we show that the local and semi-matching coloring problems are NP-complete on the class of split graphs.
- 1 January 2023
- Published by International Press of Boston in Arkiv för Matematik
- Vol. 61 (1) , 203-210
Open AccessOn local colorings of split graphs
A semi-matching coloring of a finite simple graph G=( V, E) is a mapping phi from V to {1,..., k} such that (i) every color class is an independent set, and (ii) the edge set of the graph induced by the union of any two consecutive color classes is a matching. A semi-matching coloring. is a local coloring if, in addition, (iii) the union of any three consecutive color classes induces a triangle-free subgraph of G. In this paper, we give two counterexamples and one positive solution to three problems arisen in recent papers of You, Cao, Wang. In particular, we show that the local and semi-matching coloring problems are NP-complete on the class of split graphs.
- 4 November 2022
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 151 (2) , 489-499
A separation between tropical matrix ranks
We continue to study the rank functions of tropical matrices. In this paper, we explain how to reduce the computation of ranks for matrices over the ‘supertropical semifield’ to the standard tropical case. Using a counting approach, we prove the existence of a 01 01 -matrix with many ones and without large all-one submatrices, and we put our results together and construct an n × n n\times n matrix with tropical rank o ( n 0.5 + ε ) o(n^{0.5+\varepsilon }) and Kapranov rank n − o ( n ) n-o(n) .
- 4 November 2022
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 151 (2) , 489-499
A separation between tropical matrix ranks
We continue to study the rank functions of tropical matrices. In this paper, we explain how to reduce the computation of ranks for matrices over the ‘supertropical semifield’ to the standard tropical case. Using a counting approach, we prove the existence of a 01 01 -matrix with many ones and without large all-one submatrices, and we put our results together and construct an n × n n\times n matrix with tropical rank o ( n 0.5 + ε ) o(n^{0.5+\varepsilon }) and Kapranov rank n − o ( n ) n-o(n) .
- 11 May 2021
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 149 (8) , 3173-3176
Linear mappings preserving the copositive cone
Letbe the set of all -by- symmetric real matrices, and let be the copositive cone, that is, the set of all matrices that fulfill the condition for all -vectors with nonnegative entries. We prove that a linear mapping satisfies if and only if for a fixed monomial matrix with nonnegative entries. - 11 May 2021
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 149 (8) , 3173-3176
Linear mappings preserving the copositive cone
Letbe the set of all -by- symmetric real matrices, and let be the copositive cone, that is, the set of all matrices that fulfill the condition for all -vectors with nonnegative entries. We prove that a linear mapping satisfies if and only if for a fixed monomial matrix with nonnegative entries.