$(1)$If a Arithmetic circuit $C$ has a size $x$, the degree $f_C$ should be $ \leq 2^{x-1} $? Is this bound sharp? why?

$(2)$By fingerprinted polynomial Evaluation how to determine the degree of two circuits $f_C$ and $f_{C'}$ are identical.

N.B.: Please add some references. I'm trying to find an randomized algorithm for $(2)$



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy