8
$\begingroup$

Is there an alternate proof or an exposition of the result of Grigoriev and Karpinski (STOC 1998, doi:10.1145/276698.276872) on the exponential lower bounds for Depth 3 arithmetic circuits computing $\mathsf{DET}_{n\times n}$ over a fixed finite field?

I could not understand section 2 of the paper. What is the intuition behind considering the F-linear operator $T_g$?

$\endgroup$
7
$\begingroup$

There was a subsequent extension by Grigoriev and Razborov (PS) that has a shorter exposition of proof.

$\endgroup$

Your Answer

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

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