Hauptmann P≠NP attack via polynomial hierarchy noncollapse

hi all. low-quality P vs NP “proofs” are a dime-a-dozen and scatter/ “litter” arxiv like dandelions in the grass. however, occasionally ostensibly “high quality” appearing proofs show up. that is the recent case with Hauptmann.[7]

do not want to write a lot on this subject, because have been somewhat “burned” in the past on it. but this is not an uncommon experience/ case for anyone who spends much time with these proofs (as if there is something “typical” about them, and yet history shows there is, which is both judgemental and paradoxical).

the proof is notable though, represents major effort/ background knowledge, and deserves mention. it has been around since february and a recent revision caught the eye of reddit where there is some reaction.[1] usually hear about stuff like this earlier, scan new CS titles on arxiv nearly daily, but missed it myself, maybe partly due to the authors title/ abstract style (see below). Hauptmann has great credentials; Phd and is professor at university of Bonn.[2] CS “near-janitor” Woeginger seems to have been aware of it for a few months.[3]

we had some discussion in the theory salon chat room.[6] as someone remarked there, the proof passes Aaronsons “quality” criteria for a non-crank proof which he posted soon after the deolalikar attempt roughly now ~½ decade ago.[4]

what is not well known about the deolalikar attempt that went quasi-viral in academic circles is that (only discovered this by extensive googling myself) Cook halfway endorsed it in email to colleagues. maybe partly because it used descriptive complexity techniques, something Cook specializes in.

this latest attempt seems to me to cite many very/ highly relevant papers that have run across and cited (in this blog & stackexchange writing etc) in my own long meanderings on the subject (now close to ~2½ decade). that is just a circumstantial element of course. nevertheless overall the intellectual engagement with the subject is far higher than a garden-variety crank proof.

Terence Tao magic breakthrough again with EDP, Erdos Discrepancy Problem, topnotch links

➡ ⭐ ⭐ ⭐ 💡 ❗ 😮 😀 😎 hi all. Terence Tao, who is regarded as one of the greatest living mathematicians although of course not by himself (he does not even have a picture on his “about” page), has proved the Erdos Discrepancy Problem, fresh off a profile by the NYT.[a2] Tao has the distinction as being one of the very few mathematicians who has won the $3M breakthrough award, and also has said virtually nothing about it publicly (except at the awards ceremony). he’s too busy blogging about math ofc!

the EDP is a very interesting problem that relates in some sense to patterns in random walks. functions related to primes turn out to be basically very similar to “pseudo random walks”. this has been known for decades and there is a relation to the Riemann conjecture documented by Good/ Churchhouse in 1968.[g2]

the connection of hard math/ CS problems, and automated theorem proving, with analyzing random walks is a thread Ive been pursing myself over the last few years in my Collatz conjecture research. this gives me a nice moment/ opportunity/ milestone to write it all up.

its also another huge feather in the cap of the polymath project which was peripherally involved in the solution and a big triumph for cyber-collaborative mathematics.[b] a now-near-legendary almost-offhand musing in a blog comment led Tao in the right direction. “the devil is in the details…” 😈

Kalai is already casting around for the next “Big Kahuna”. any ideas? [b14] 😉 😀

Backurs, Indyk connect strong exponential time hypothesis to edit distance; other CS time/ space hierarchy/ continuum news

hi all. recently Backurs/ Indyk just got a paper accepted into STOC 2015 connecting the Strong Exponential Time Hypothesis (“SETH”) with tight bounds on computing edit distance. the latter has many applications across CS and also plays a big role in bioinformatics and computational biology wrt DNA sequences where it relates to natural alterations, ie more specifically “biologically occurring genetic processes”—eg even occuring in our own bodies… and surely cant get more “applied” than that!

there is some buzz/ excitement on this result as this is regarded as something of a breakthrough. it reminds me of the concept of “the microcosm reflects the macrocosm and vice versa” aka/ in short, “as above, so below”. a polynomial time algorithm speed (“the small”) seems to have major implications for speed of NP complete problems wrt exponential time (“the large”) and vice versa.[a]

⭐ ➡ and moreover/ further, near-dramatic connection/ exhibition/ manifestation/ confirmation of an apparent deep/ recurring principle/ theme/ “design pattern” in CS, interconnection/ interdependency of upper and lower bounds. at times upper and lower bounds seems like the yin and yang of TCS… 💡 😮 ❤

leading authorities weigh in on P vs NP proofs

hi all more timely spring cleaning out my mountains of link piles. P vs NP has been a big topic in this blog but have pulled back on it somewhat myself to chase Collatz circles (surely equally impossible but still yet lower hanging fruit? does that make any “zen” sense?). but am always tracking it near at hand.

within the last year there have been a few notable blogs by leaders on the value of P vs NP proof attempts. RJLipton, Fortnow, Trevisan (a trifecta completed recently & partially triggering this post). there was also an archiv paper by undergraduate students of Hemaspaandra. usually there is a policy of “omerta”-like silence on these attempts. so its quite remarkable that these experts/ authorities are engaging with and/ or defending the efforts to some degree.

have been studying P vs NP attempts since the early 2000s or so (“intermittently”!). think they have some “)(” value but with great qualification on that. experts are busy and should never feel obligated to pay any attention. but encouraging others to attempt to respond in some way seems positive & minimally risky.

what truly amazes me are how many of these “attempts” (actually claims) that are by Phds, some of them from very elite schools worldwide. now one would not be surprised that attempts by undergraduates or people who have not even attended college would be bogus and not have much value. but when very highly trained Phds come up with unintelligible papers, it would seem to call into question our educational system to “some degree”. & so far no comment by any experts on that angle…

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]