Category Archives: cstheory

math celebration 2016: pythagorean triples empirical attack conquest


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

alphaGo victorious 4-1 over Sedol in SKorea, NKorea crushes Warmbier 15-0

hi all the go match was very eventful and turned out to have massive media coverage worldwide, with huge interest from technology publications, and theres a sizeable AI/ ML/ singulatarian crowd on the internet that follows these types of developments quite avidly.

wish that google would transcribe the press conferences. there was a lot of interesting details but it takes a long time to watch them and the midstream translation interruption (korean to english, english to korean) slows down the presentation also.

saw some interesting press questions in the post-3rd match conference iirc that tie in with some angles explored on this blog.

Continue reading