We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. ... more >>>

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings,and each leaf is assigned an $\ell$-bit string.
The desired output is the value of the root, where ... more >>>

We present a deterministic $2^{k^{\mathcal{O}(1)}} \text{poly}(n,d)$ time algorithm for decomposing $d$-dimensional, width-$n$ tensors of rank at most $k$ over $\mathbb{R}$ and $\mathbb{C}$. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes $2^{k^{k^{\mathcal{O}(k)}}} \text{poly}(n,d)$ time and the deterministic $n^{k^k}$ time algorithms of Bhargava, Saraf, ... more >>>