Lower bound for constant degree monotone arithmetic circuits

Question

Do we know an explicit constant degree polynomial that requires monotone arithmetic circuits of size $n^{10}$?

Answer 1

The Nisan--Wigderson polynomials are one example. That is, let $$ \mathrm{NW}_{n,m,d}(\vec{x}) := \sum_{\substack{p(t) \in \mathbb{F}_m[t] \\ \deg(p) \le d}} x_{1,p(1)} \cdots x_{n,p(n)}. $$ Let $k$ be your favorite constant and consider the polynomial $\mathrm{NW}_{3k,m,k}$. This is a polynomial in $3mk$ variables of degree $3k$. One can show that $\mathrm{NW}_{3k,m,k}$ requires monotone arithmetic circuits of size $m^k$. More details can be found in Section 8.2 (in particular, Theorem 8.8) of Ramprasad Saptharishi's survey on algebraic circuit lower bounds.