the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary:

is this new paper Sums of products of polynomials in few variables : lower bounds and polynomial identity testing / Kumar, Sarif essentially stating that a particular exponential lower bound on 2-depth arithmetic circuits ($\Sigma \Pi$) would imply VP$\neq$VNP?

(understood as cited by Fortnow the 4-depth case has been proved elsewhere by Kayal, Saha, Saptharishi.)

are the results proved in this paper or earlier papers? also if anyone knows of (introductory) textbook formulation(s) of this theory, most of which is contained in papers, please cite it.

  • $\begingroup$ Have you read the paper? You ask if "the results" are proved in the paper; if so, the way to find out is to read the paper. (Also, it's not clear to me what results you mean by "the results".) Finally, please use proper English. "am looking for a more layman-readable summary" is not proper grammar. Don't be lazy. This is not a message board where you can use shorthands like that; we expect you to use proper English, proper capitalization, proper grammar. $\endgroup$ – D.W. Apr 25 '15 at 3:11
  • $\begingroup$ I'm also confused what you mean with "are the results proved in this paper or earlier papers?" Can you clarify that? The rest of the last paragraph seems like a separate question, and it might possibly be a new question. $\endgroup$ – Juho May 19 '15 at 16:35
  • $\begingroup$ @Juho skimmed the paper. not an expert, hence asking for layman understanding. experts on this seem to be rather rare. have little interest in anyones feedback who havent read or at least skimmed the paper either. further thought it seems to be mainly a depth 3 result in the paper, the main result outlined in the abstract. the "result" is as in the highlighted quote. ie is there a depth 3 formulation of VP=?VNP & is that whats in the paper. since asking wrote rough survey of area $\endgroup$ – vzn May 19 '15 at 17:40

Your Answer

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

Browse other questions tagged or ask your own question.