
PreviousNext
We investigate the behavior of the non-negative rank of a matrix, $\hbox{rk}_+$, on Kronecker product, $\times$. Beasley et al. [2013] constructed matrices with $\hbox{rk}_+(M\times M)$ strictly smaller than $\hbox{rk}_+(M)^2$.
We will show that i) there exists an $M$ with $\hbox{rk}_+(M\times M)\leq O(\hbox{rk}_+(M)\log(\hbox{rk}_+(M))$.
Defining asymptotic non-negative rank as $\overline{\hbox{rk}}_+(M):= \lim_{k\rightarrow ... more >>>
We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant ... more >>>
Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue ... more >>>
PreviousNext