arithmetic circuit complexity, Valiants VP=?VNP, recent advances/ breakthroughs, new directions

⭐ 💡 ❗ ❓ hi all. recently there have been some interesting results on arithmetic circuit complexity as cited by fortnow, which relates the classes VP/VNP invented by valiant over ~3½ decades ago. the VP=?VNP problem has been reduced to a depth-4 circuit question which is very impressive and maybe verging/ bordering on a breakthrough, afaik for 1^st time reducing it to a finite/ constant depth.[a1][a7][a8] (shades/ echoes of Zhangs 2013 breakthrough?) there are also recent results that seem to advance the depth 3 case significantly.[a9]

alas though the connection to VP=?VNP to P=?NP is apparently not very strong, but there has been shown to be a collapse in the complexity hierarchy by Burgisser if they (that is the former (V)NP!) are proven to be equal… (get this… wait for it…) assuming the Generalized Riemann Hypothesis![a13]

apparently a framework/ problem/ conjecture in this area provably equivalent to P vs NP has not yet been made, but its not so implausible to think that a P=?NP or P/poly=?NP type connection could be (eventually) constructed in this area. in fact given its history & directions, it seems almost inevitable.

there are a lot of great surveys.[a1][a2][a3][a4][a5] but alas a lot of this is outside of streamlined/ polished textbook presentations.

the field catches my eye because have long conjectured, and as written up about ~2½ yr ago (near/ shortly after the birth/ launch of this blog & in fact part of its original inspiration/ rationale/ raison d’être) that there is a strong connection between “factoring” monotone boolean circuits, which can be written in expressions closely resembling multivariate polynomials, and P vs NP. and recently factoring multivariate polynomials has been shown to have some deep connections to polynomial identity testing,[a10] which in turn with recently announced results (apr23^rd! & maybe some of the key motivation/ inspiration/ tipping point/ trigger for this post!) now seems to be connected to some results in arithmetic circuit complexity, also depth 3 circuits.[a6]

so far there are not much research or strong connections made between boolean/ monotone circuits and arithmetic circuits — there are some papers but it would be a quite a challenging exercise to survey them… any takers? — nevertheless there is some sign of overlap, eg Berkowitz has worked in both areas. (he is the author of one of the standout results in monotone circuit complexity relating to slice functions cited in my earlier P=?NP conjecture/ “outline” blog.) acc wikipedia/ algebraic circuits: “One benchmark in our understanding of the computation of polynomials is the work of Valiant, Skyum, Berkowitz and Rackoff.[4] They showed that if a polynomial f of degree r has a circuit of size s, then f also has a circuit of size polynomial in r and s of depth O(log(r) log(s))”

lower bounds are a notoriously difficult area and these new advances ought to definitely be celebrated by the wider community, and they might even be some milestones/ signposts signalling/ pointing to some longterm/ ultimate eventual success of the circuit program, but alas it seems there are not that many people paying attn to this field. there is one lucky 24v mathoverflow question so thats a modest )( encouraging sign that its not merely a narrow/ abstruse area/ niche inside TCS.[a11]

the papers share a lot of the same (indian) authors who are clearly very dedicated to this area but maybe its not a large group or audience. this seems somewhat unjustified given its significance and recent advances. but, scientists are a conservative bunch.

a few of my own questions on the stackexchange sites [a12][a14][a15] dont seem to be getting much attn, ofc that could be due to (after ~3½+ yr) ppl just ignoring me (as usual?) lol 😐 … the small )( good news is they havent been closed so far

← you can tell am excited/ ebullient because (ofc all the typical effusive emoticons, italics, too many adjectives, generally overwrought style, etc), but am running through the generally risky/ thankless/ nervewracking gauntlet of asking SE questions, and meticulously referencing/ footnoting this blog, every single link!

← hey thats ok am quite proud of my few “scattered” tumbleweed badges on the SE sites. 😎 😀 … and even the closed/ vaporized questions are my SE battle scars … aka the pioneers are the ones with the arrows in their backs! 😈

a. vnp

• 1. Recent Progress on Arithmetic Circuit Lower Bounds | Saptharishi | Bulletin of EATCS
• 2. Arithmetic Circuits: a survey of recent results and open questions / Shpilka, Yehudayoff
• 3. Characterizing Valiant’s algebraic complexity classes / Malod, Portier
• 4. [1307.3863] Algebraic Complexity Classes / Mahajan
• 5. Algebraic Complexity Classes / Mahajan – Springer
• 6. [1504.06213] Sums of products of polynomials in few variables : lower bounds and polynomial identity testing / Kumar, Saraf
• 7. ECCC – TR13-091 – A super-polynomial lower bound for regular arithmetic formulas. / Kayal, Saha, Saptharishi
• 8. ECCC – TR14-005 – An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas / Kayal, Limaye, Saha, Srinivasan
• 9. ECCC – TR15-073 – Lower Bounds for Sums of Products of Low arity Polynomials / Kayal, Saha
• 10. Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization / Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
• 11. computational complexity – Algebraic P vs. NP – MathOverflow
• 12. complexity theory – 2-depth arithmetic circuits and VP vs VNP / vzn – Computer Science Stack Exchange
• 13. cc.complexity theory – Does $VP \neq VNP$ imply $P \neq NP$? – Theoretical Computer Science Stack Exchange
• 14. cc.complexity theory – analogies between VNP and NP – Theoretical Computer Science Stack Exchange
• 15. cc.complexity theory – intuition that VP=?VNP is (not?) connected to P=?NP – Theoretical Computer Science Stack Exchange
• 16. Valiants Permanent Contributions / RJLipton blog
• 17. Algebraic Complexity Theory / Bürgisser, Clausen, Shokrollahi
• 18. Completeness and Reduction in Algebraic Complexity Theory / Bürgisser
• 19. Partial Derivatives in Arithmetic Complexity and beyond / Xi Chen, Neeraj Kayal, and Avi Wigderson
• 20. A selection of lower bounds for arithmetic circuits / Neeraj Kayal and Ramprasad Saptharishi

Advertisements