Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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