<p>The Nisan--Wigderson polynomials are one example. That is, let
<span class="math-container">$$
\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)}.
$$</span>
Let <span class="math-container">$k$</span> be your favorite constant and consider the polynomial <span class="math-container">$\mathrm{NW}_{3k,m,k}$</span>. This is a polynomial in <span class="math-container">$3mk$</span> variables of degree <span class="math-container">$3k$</span>. One can show that <span class="math-container">$\mathrm{NW}_{3k,m,k}$</span> requires monotone arithmetic circuits of size <span class="math-container">$m^k$</span>. More details can be found in Section 8.2 (in particular, Theorem 8.8) of <a href="https://github.com/dasarpmar/lowerbounds-survey" rel="nofollow noreferrer">Ramprasad Saptharishi's survey</a> on algebraic circuit lower bounds.</p>

CC BY-SA 4.0
2023-11-13T20:39:27.653Z
Thank you! That is exactly what I was looking for.
ivmihajlin
CC BY-SA 4.0
2023-11-13T19:46:51.690Z
2023-11-13T19:46:51.690Z
Robert Andrews
<p>Do we know an explicit constant degree polynomial that requires monotone arithmetic circuits of size <span class="math-container">$n^{10}$</span>?</p>

<lower-bounds><arithmetic-circuits><monotone>
Lower bound for constant degree monotone arithmetic circuits
ivmihajlin
# Lower bound for constant degree monotone arithmetic circuits

(Asked by: username_0 on 2023-11-12)

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

**Tags:** lower-bounds, arithmetic-circuits, monotone


---

## 1 answers

### Answer by username_1 on 2023-11-13. Score: 4 | Accepted answer

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](https://github.com/dasarpmar/lowerbounds-survey) on algebraic circuit lower bounds.

> **Comments:**
> **username_0**: Thank you! That is exactly what I was looking for.  

---

