I was reading the Survey on Polynomial Identity Testing by Nitin Saxena. In the Depth 3 Blackbox PIT Algorithm he first finds $O(k^2d^2+2^k)$ many subspaces of the linear forms of the $\sum\prod\sum(n,k,d)$ circuit and claims that for any linear transformation $\tau$, rank of these subspaces. Suppose the circuit is nonzero to begin with.

Then he said if $\tau(C)=0$ then the rank bounds entails that either $\tau(C)$ is not minimal or $rank(\tau(C))<R(k,d)$ where $R(k,d)$ is rank bound. Why if $\tau(C)$ is not minimal this rank bound case is coming.

Also if the latter case happens why it implies $rank(C)<R(k,d)$ and why it implies $C$ idself is 0



Your Answer

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