norbert blum P vs NP attack goes CYBER-SCIENCE-VIRAL!

⭐ 💡 ❗ 😀 😎 ❤ hi all! want to write a lot on this, have all kinds of impressions and things to say on one of my favorite topics in the world for 2½ decades now and which this blog is partly dedicated to, but am starting out by just collecting some links vacuumed up mostly today for others to check out, the top locations for commentary. unf there is not really a key/ central place so far where all the action is happening. will be adding to this post as time goes on. its very hard to figure out when to time a post wrt very fast moving developments like this, but my trigger just hit mostly right after RJLipton[a10] blogged about it. oh yeah, that comment by gowers that “I think it may reach the level where the experts feel that it needs to be checked” is highly triggering for me too (referring ofc to himself in 3rd person, maybe being more than a bit )( coy about this— doncha just love hardcore mathematicians! which reminds me of the joke about shoelaces…) … oh and then theres also fortnow who literally wrote the book on it! (oh yeah wrt that theres this by RJL too!) 😛

it looks like the Norbert Blum paper[a14][a15] basically went “pop/ scientific viral” today or so probably after mentions on Reddit[a8][a9] and Hacker News.[a11] of the experts Trevisan[a1] was the first to wager a reaction along with some curious onlookers like Baez[a2] and verging-on-jester-or-gadfly-or-even-troll Motl[a5] who along with some mild conspiracy theory about CS research(ers) (lol!) says, wrt the #1 top problem in TCS…

Except that unlike the case of string theory, there exists absolutely no rational evidence that there exists something stunning waiting to be discovered.

@#$% 😡 👿 ❗ whoa, fighting words and/ or near-sacrilege there! excuse me, what is “stunning” is that the problem with $1M prize over 1½ decade has eluded/ stymied/ thwarted the worlds greatest scientific minds for almost ½ century now! and the proof either way, in whatever shape or form, will be assuredly stunning to anyone who isnt jaded or a nihilist! hey physics bozo! think of a great experiment that guaranteed leads to an extraordinary answer either way! arent there any examples like that in your field anyway? or is maybe someone looking a little envious over there? or out of the loop or maybe dont even know how to flirt at all?

the TCS stackexchange post by a n00b newbie (who didnt know enough to not ask! hows that for “zen beginners mind”?) is now up to 136-4 votes and 28K hits (thursday eve 8/17).[a3] (joy that the lame heavyhanded/ constricting/ dictatorial policy of the self-appointed cyber spoilsports and partypoopers also long criticized here in this blog, is overruled by striking mass opposition!) that post slipped my radar for a few days! found the paper on the 1st day (monday this wk) but thought it might stay “unviral” (you know, like those killer viruses locked in the… thawing… arctic, right?) based esp on the last Hauptmann attempt.[a12][a13]

discovered the big commotion today via reddit myself and spent excited hours poking through sites! but my hits on the Hauptmann blog post had been creeping/ climbing up massively all week, merely from google searches (many from germany), and figured it was due to questions on the Blum attempt. turns out theyre both profs at the same university! (Bonn/ Germany) pardon me but wtf?!?… some kind of story there eh? are any reporters listening?

cyberspace is such a joy sometimes, in my quasi-bipolar days, mostly-sometimes seemingly very flat for days, weeks, months, even years at a time, this is a massive manic spike for me… the adrenalin is flowing! didnt sleep as well this week! there is so much cybersynchronicity to this, must admit, its a very rare event, am myself (and defensively, some others are too) having a bit of a mini-cyber-orgasm so far… 💡 😮 🙄 ❗

Advertisements

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…