Category Archives: cstheory

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? :mrgreen:

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… 💡 😮 o_O 🙄 ❗

Continue reading

Advertisements

math celebration 2016: pythagorean triples empirical attack conquest

310516_proofsupercomputer_1

actual U Texas Stampede supercomputer where proof was run [a2]

➡ 💡 ❗ ⭐ 😎 😀 hi all. RJLipton recently covered the amazing/ brilliant breakthrough of solving the pythagorean triples problem by empirical work namely a reduction to SAT and analysis by a supercomputer by Heule, Kullmann, Marek and its a nice pivotal trigger/ tipping point for my own writeup along with related stuff.[a] (have been waiting for opportune time to write this up since may.) proofs like these are a complex or “complicated relationship” for mathematicians (aka facebook-speak), a love-hate affair. (did the extraordinary/ breakthrough/ revolutionary/ paradigm-shifting 4-color computer proof ever win any awards? and how much despair/ handwringing and further effort has there been over it over the decades?)

the breakthrough is celebrated but mathematicians would like to see shorter proofs that are human-comprehensible, so there are mixed/ ambivalent feelings about it within the community. have written on this topic quite at length in this blog even since its beginnings, and this latest breakthrough is delightfully affirmationally crosscutting across many of this blogs categories, and think this is the tip of the iceberg of 21st century mathematics in a way not yet fully recognized. its a dramatic, vivid realization/ materialization of an idea suggested a few years ago here called “SAT induction.” think that these types of proofs will lead to new theory that is indeed human comprehensible but some of the isolated theorems will be claimed first by computer analysis before the more thorough theory catches up to integrate them.

Continue reading

Turing 2016 tribute and the notorious SE chat ad saga

turing-statue.jpghi all this eponymously named blog was started a few months after Turing centennial birthday in 2012.[1][19] so far there hasnt been much writing on him here except for around 2014 when the Imitation Game movie came out.[23] finally time to fill that (unfillable) gap some. Turings birthday passed in june and was hoping to time this post with it (its been on my “to do” pile for months now).

Turing was an inspiration to me since a teenager, mainly through the writing of Hofstadter and his remarkable books, Godel Escher Bach and Metamagical Themas (these books are near-legendary for inspiring nearly an entire generation of computer scientists…). the deep mystery of Turing machines transfixed me, and later realized it was tied with emerging research into “complexity theory”. how could such a simple yet ingenious object capture such incredible complexity, almost subsume mathematics itself? it seems a question that is still being investigated and answered and maybe at the heart of continued advances.

even at young age it also seemed to me the concept of undecidability had some kind of unfinished or provisional aspect to it, that it wasnt the complete story somehow. apparently mathematicians attacked nearly undecidable problems all the time to come up with some kind of proofs anyway. isnt this some kind of deep paradox? over the years/ decades have delved into this deep mystery myself and added some degree of awareness/ insight, but in many ways feel its still mostly unresolved. as Nietzsche said, “when you stare deeply into the abyss, the abyss stares back.”

Continue reading

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.

Continue reading

number theory news/ highlights: prime bias, Diffie-Hellman, Zhang-Tao, Wiles, Riemann

PrimesResearchers😮 💡 ❗ 😎 😀 ❤ hi all. big news in number theory last few months and years. this is a tribute to a few years of top breakthroughs and exciting developments. the general theme is “primes” but there are a few detours.

in a breakthru/ rare event, a new statistical property of primes was discovered related to frequency of occurrence digits in base-n expansions. it was discovered by Oliver/ Soundararajan and has led to a huge amount of media attention and notice by top scientists. some of it was uncovered with dear-to-my-heart computer empirical/ experimental approaches.[e]

yet its somewhat reminiscent of another similar discovery only ~7yrs ago in 2009 by Luque/ Lacasa.[e6]

big discoveries like this sometimes make one think that maybe we havent even “scratched the surface” of theory of primes. [a2], a long-held/featured link on this site (on main sidebar) points out connections with quantum mechanics by Sautoy, an authority on the Riemann hypothesis (Dyson/ Montgomery 1972).

speaking of Riemann, and apropos/ befitting/ in observation/ reverence of todays date, it was claimed to be proven by a Nigerian recently. and it turns out not surprisingly Nigerian mathematics is not all so different than illustrious Nigerian business ventures advertised on the internet.[g]

Continue reading