0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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. ♦
    Commented Apr 25, 2015 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
    Commented May 19, 2015 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
    Commented May 19, 2015 at 17:40

0

Reset to default

Your Answer

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