New answers tagged algebraic-complexity
5
votes
Accepted
Some polynomials in $\mathbb{F}[x]$ require $O(\sqrt{d})$ circuit size
I don’t know where the lower bound comes from as Wigderson gives no reference, but it is suboptimal. One can easily prove the following bound:
Proposition: For any field $F$ and $d\in\mathbb N$, ...
- 18.6k
Top 50 recent answers are included