36 citations · 161 across the 31 of their papers we have counts for
9 papers · 1 filter
A counterexample to Strassen's direct sum conjecture
Yaroslav Shitov
The rank of tensors is not additive with respect to the direct sum.
On the complexity of graph coloring with additional local conditions
Yaroslav Shitov
Let be a finite simple graph. Recall that a proper coloring of is a mapping such that every color class induces an independent set. Such a $…
A separation between tropical matrix ranks
Yaroslav Shitov
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 th…
On tropical and nonnegative factorization ranks of band matrices
Yaroslav Shitov
Matrix factorization problems over various semirings naturally arise in different contexts of modern pure and applied mathematics. These problems are very hard in general and cause…
Low-Rank Matrix Approximation in the Infinity Norm
Nicolas Gillis, Yaroslav Shitov
The low-rank matrix approximation problem with respect to the entry-wise -norm is the following: given a matrix and a factorization rank , find a matrix w…
Three observations on spectra of zero-nonzero patterns
Yaroslav Shitov
Using standard techniques from combinatorics, model theory, and algebraic geometry, we prove generalized versions of several basic results in the theory of spectrally arbitrary mat…
A counterexample to Comon's conjecture
Yaroslav Shitov
We present an example of a symmetric tensor of size which can be written a sum of simple tensors with complex entries but not as a sum of symm…
Column subset selection is NP-complete
Yaroslav Shitov
Let be a real matrix and let be a positive integer. In the column subset selection problem (CSSP), we need to minimize the quantity , where can be…
A counterexample on spectra of zero patterns
Yaroslav Shitov
An zero pattern , which is a matrix with entries and , is called spectrally arbitrary with respect to a field if any monic polynomial of degree ca…