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

462016_orig⭐ 💡 ❗ ❓ 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 1st 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 (apr23rd! & 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 o_O

← 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
Advertisements

2 thoughts on “arithmetic circuit complexity, Valiants VP=?VNP, recent advances/ breakthroughs, new directions

  1. Pingback: Arithmetic Circuit Complexity, Recent Advances | Tambo University

  2. Pingback: Boolean Circuit Complexity;Recent Advance. | Tambo University

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s