We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>>

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $\exp(\Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $\exp(\tilde{\Omega}(\sqrt{n})).$

more >>>