Yaroslav N. Shitov

activity

20102020

most citedAn improved bound for the length of matrix algebras

36 citations · 161 across the 31 of their papers we have counts for

collaborators

42 papers

math.CO2020

A sign pattern with non-zero elements on the diagonal whose minimal rank realizations are not diagonalizable over the complex numbers

Yaroslav Shitov

The rank of the $9 \times 9$ matrix $$ \left( \begin{array}{cccc|c|cccc} 1&1&0&0&1&0&0&0&0\\ 1&1&0&0&0&0&0&0&0\\ 0&0&1&1&1&0&0&0&0\\ 0&0&1&1&0&0&0&0&0\\\hline 0&0&0&0&1&0&1&0&1\\\hl…

math.CO2019

Linear mappings preserving the copositive cone

Yaroslav Shitov

Let $S_{n}$ be the set of all $n$ -by- $n$ symmetric real matrices, and let $C_{n}$ be the copositive cone, that is, the set of all matrices $a \in S_{n}$ that…

math.CO2019

Counterexamples to Hedetniemi's conjecture

Yaroslav Shitov

The chromatic number of $G \times H$ can be smaller than the minimum of the chromatic numbers of finite simple graphs $G$ and $H$ .

math.CO2019★ 1 cited

The ring $M_{8 k + 4} (Z_{2})$ is nil-clean of index four

Yaroslav Shitov

We show that the direct sum of an odd number of matrices $C = 0100001000011001$ cannot be a sum $P + Q$ of matrices…

math.CO2019

One more counterexample on sign patterns

Yaroslav Shitov

The \textit{sepr-sequence} of an $n \times n$ real matrix $A$ is $(s_{1}, \dots, s_{n})$ , where $s_{k}$ is the subset of those signs of $+, -, 0$ that appear in the values of the $k \times k$ …

math.CO2019

An improvement to a recent upper bound for synchronizing words of finite automata

Yaroslav Shitov

It has been known since the 60's that any complete discrete $n$ -state automaton admits a reset word of length not exceeding $α n^{3} + o (n^{3})$ for some absolute constant $α$ . J.-E. Pin…

math.AC2018★ 7 cited

Quantum version of Wielandt's Inequality revisited

Mateusz Michałek, Yaroslav Shitov

Consider a linear space L of complex D-dimensional linear operators, and assume that some power L^k of L is the whole space of DxD matrices. Perez-Garcia, Verstraete, Wolf and Cira…

math.CO2018★ 36 cited

An improved bound for the length of matrix algebras

Yaroslav Shitov

Let $S$ be a set of $n \times n$ matrices over a field $F$ . We show that the $F$ -linear span of the words in $S$ of length at most $2 n lo g_{2} n + 4 n$ is the full $\m…

math.CO2017★ 8 cited

A counterexample to Strassen's direct sum conjecture

Yaroslav Shitov

The rank of tensors is not additive with respect to the direct sum.

math.CO2017

On the complexity of graph coloring with additional local conditions

Yaroslav Shitov

Let $G = (V, E)$ be a finite simple graph. Recall that a proper coloring of $G$ is a mapping $φ : V \to {1, \dots, k}$ such that every color class induces an independent set. Such a $…

math.CO2017

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…

math.CO2017

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…

cs.CC2017★ 20 cited

Low-Rank Matrix Approximation in the Infinity Norm

Nicolas Gillis, Yaroslav Shitov

The low-rank matrix approximation problem with respect to the entry-wise $ℓ_{\infty}$ -norm is the following: given a matrix $M$ and a factorization rank $r$ , find a matrix $X$ w…

math.CO2017

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…

math.CO2017

A counterexample to Comon's conjecture

Yaroslav Shitov

We present an example of a symmetric tensor of size $800 \times 800 \times 800$ which can be written a sum of $903$ simple tensors with complex entries but not as a sum of $903$ symm…

math.CO2017

Column subset selection is NP-complete

Yaroslav Shitov

Let $M$ be a real $r \times c$ matrix and let $k$ be a positive integer. In the column subset selection problem (CSSP), we need to minimize the quantity $∥ M - S A ∥$ , where $A$ can be…

math.CO2017★ 4 cited

A counterexample on spectra of zero patterns

Yaroslav Shitov

An $n \times n$ zero pattern $S$ , which is a matrix with entries $*$ and $0$ , is called spectrally arbitrary with respect to a field $F$ if any monic polynomial $f$ of degree $n$ ca…

math.CO2016★ 1 cited

Counterexamples on spectra of sign patterns

Yaroslav Shitov

An $n \times n$ sign pattern $S$ , which is a matrix with entries $0, +, -$ , is called spectrally arbitrary if any monic real polynomial of degree $n$ can be realized as a characterist…

math.CO2016★ 21 cited

How hard is the tensor rank?

Yaroslav Shitov

We investigate the computational complexity of tensor rank, a concept that plays fundamental role in different topics of modern applied mathematics. For tensors over any integral d…

math.CO2016

Which semifields are exact?

Yaroslav Shitov

Every (left) linear function on a subspace of a finite-dimensional vector space over a (skew) field can be extended to a (left) linear function on the whole space. This paper explo…

math.CO2016

On the complexity of failed zero forcing

Yaroslav Shitov

Let $G$ be a simple graph whose vertices are partitioned into two subsets, called filled vertices and empty vertices. A vertex $v$ is said to be forced by a filled vertex $u$ if $v…

math.CO2016

Euclidean distance matrices and separations in communication complexity theory

Yaroslav Shitov

A Euclidean distance matrix $D (α)$ is defined by $D_{ij} = (α_{i} - α_{j})^{2}$ , where $α = (α_{1}, \dots, α_{n})$ is a real vector. We prove that $D (α)$ cannot be written as a sum of $\left[2\sqrt…

math.CO2016

Coloring the power graph of a semigroup

Yaroslav Shitov

Let $G$ be a semigroup. The vertices of the power graph $P (G)$ are the elements of $G$ , and two elements are adjacent if and only if one of them is a power of the other.…

math.CO2016

The complexity of positive semidefinite matrix factorization

Yaroslav Shitov

Let $A$ be a matrix with nonnegative real entries. The PSD rank of $A$ is the smallest integer $k$ for which there exist $k \times k$ real PSD matrices $B_{1}, \dots, B_{m}$ , $C_1,\ldots…

A sign pattern with non-zero elements on the diagonal whose minimal rank realizations are not diagonalizable over the complex numbers

Linear mappings preserving the copositive cone

Counterexamples to Hedetniemi's conjecture

The ring M8k+4​(Z2​) is nil-clean of index four

One more counterexample on sign patterns

An improvement to a recent upper bound for synchronizing words of finite automata

Quantum version of Wielandt's Inequality revisited

An improved bound for the length of matrix algebras

A counterexample to Strassen's direct sum conjecture

On the complexity of graph coloring with additional local conditions

A separation between tropical matrix ranks

On tropical and nonnegative factorization ranks of band matrices

Low-Rank Matrix Approximation in the Infinity Norm

Three observations on spectra of zero-nonzero patterns

A counterexample to Comon's conjecture

Column subset selection is NP-complete

A counterexample on spectra of zero patterns

Counterexamples on spectra of sign patterns

How hard is the tensor rank?

Which semifields are exact?

On the complexity of failed zero forcing

Euclidean distance matrices and separations in communication complexity theory

Coloring the power graph of a semigroup

The complexity of positive semidefinite matrix factorization

The ring $M_{8 k + 4} (Z_{2})$ is nil-clean of index four