Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P$ if for every $x\in \{0,1{\}}^n$ we have that $C(x)=P(x)$. This is in contrast to syn…