4
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you! That is exactly what I was looking for. $\endgroup$
    – ivmihajlin
    Commented Nov 13, 2023 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.