Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

share|cite|improve this answer

Your Answer


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.