11 ms·
Knuth on Huang's Sensitivity Proof: “I've got the proof down to one page” [pdf]
- AnimalMuppet 7y agoMore like two thirds of a page - the bottom third is "notes" which are not really part of the proof!
- TheRealPomax 7y agoWhen it comes to a proof, there are no notes. Just "Weirdly small typeset text off to the side that should have been in the main body".
- usmannk 7y agoIn this case the notes don’t support the proof but rather explore alternatives.
- dang 7y agoWe changed the URL from https://www.cs.stanford.edu/~knuth/papers/huang.pdf https://www.cs.stanford.edu/~knuth/papers/huang.pdf to where Knuth actually said that.
- quxbar 7y ago:') it's like watching a really great game of baseball
- gHosts 7y agoGolf.https://code-golf.io/ https://code-golf.io/ Mathematical golfing
- shubrigast 7y agoRelated: dwitter.net
- doe88 7y agoOne thing is certain reading a mathematical proof from Knuth is TeX and its beauty will be used ;)
- pdpi 7y agoI find it quite amusing that the venue where he announced[0] his more compact proof mangled word wrapping as badly as it did. 0. https://imgur.com/E1Xrzvf https://imgur.com/E1Xrzvf
- devnulloverflow 7y agoYou are amused that the Web has worse typography than TeX???
- lonelappde 7y agoHow would TeX render that sentence with a long link in a small column?
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]
- espeed 7y agoNB: Proof announcement thread from a few weeks ago... Sensitivity Conjecture Resolved https://news.ycombinator.com/item?id=20338281 https://news.ycombinator.com/item?id=20338281
- emmelaich 7y agoNot a link to a pdf, despite the HN title. It's a link to Knuth's comment which has a link to the pdf. [edit; saw dang's comment just now which says the HN link has changed.]
- zcbenz 7y agoHuang's comment is also very interesting: > Regarding how long it took me to find this proof, here is the timeline for those who are interested. https://www.scottaaronson.com/blog/?p=4229#comment-1813116 https://www.scottaaronson.com/blog/?p=4229#comment-1813116
- krastanov 7y agoThe gargantuan intellectual effort behind this is incredibly humbling. I can hardly imagine the breadth of knowledge one needs to be able to keep in their mind to tackle this problem.
- JJMcJ 7y agoNot sure on this, but it is said the Fermat's Last Theorme proof involved most every area of modern mathematics. Andrew Wiles was so productive he dribbled out older results to hide the fact he was 100% on the Fermat problem for years. Huang and Knuth are pretty smart as well it seems like.
- hilbertseries 7y agoThe proof of Fermats last theorem did not involve many areas of mathematics. It was primarily proved via algebraic geometry. That’s also not true about wiles productivity... he first discovered the proof in 93 but then when he talked to people about it an error was found. He eventually fixed the error in 94 and then in 95 it was published. No mathematician waits to publish the proof of one of the greatest unsolved problems in mathematics.
- insulanus 7y agoThe above comment is talking about Wiles slowly giving out unrelated results he had saved up before starting on Fermat's last Theorem in earnest.
- tempguy9999 7y agoHere's a quote from Richard Bellman, from his paper on the birth of dynamic programming <<<What is worth noting about the foregoing development is that I should have seen the application of dynamic pro- gramming to control theory several years before. I should have, but I didn’t. It is very well to start a lecture by saying, ‘Clearly, a control process can be regarded as a multistage decision process in which???,’ but it is a bit misleading. Scientific developments can always be made logical and rational with sufficient hindsight. It is amazing, however, how clouded the crystal ball looks beforehand. We all wear such intellectual blinders and make such inexplicable blun- ders that it is amazing that any progress is made at all>>> In simpler, personal terms, "oh you bloody idiot, why didn't you XYZ...?" I was considering a problem related to a new data structure. There was a part that was plain ugly, just stank. I thought I could do better, so expressed the problem as a programmer might, and looked for regularity. There was a lot of regularity, so there was an underlying structure which I could grasp at, but not reach. Grab, grab, grab. It was like mist. I realised it involved the edges of an n-dimensional cube. I could see the 2D case, it's trivial, so what did I do? Well I needed to generalise it so I went for the 4D cube. I spent literally weeks muttering to myself like a nutter, half the time wandering like a zombie. And eventually it clicked. I may, just may have found something new and genuinely useful in combinatorics but that's not the point. The point is, had I gone from the 2D case to the 3D case the structure I was looking for would have dropped out in an afternoon. Weeks wasted. It was so simple, you bloody idiot, why didn't you... I'm not a mathematician, but I guess a lot of maths is like that. (Edit: quoted Bellman extract to delineate it properly)
- oneepic 7y agoThe Don. Quite a fast turnaround too.
- copperx 7y agoIsn't Knuth about 80 years old? If that isn't humbling, I don't know what is.
- oneepic 7y agoAnd he's still working on TAOCP.
- antupis 7y agoI would donate my kidney if I would be half of bright as Knuth in 81 years old.
- pjmorris 7y agoI would donate my kidney if it'd help Knuth live long enough to finish his series!
- aryamaan 7y agoNot to innuade the value from his books; but I do have a question. Are his books useful for someone who are into improving his daily-job-programming skills? I gave a look at the indexes of his books, they seems more relevant for when I was into algorithmic programming competitions.
- dancek 7y agoThe answer to that question may come down to philosophy. Does it help your daily work to really understand things that are only slightly connected to what you are doing? I've only read a tiny bit of TAOCP but I believe reading it would be quite useful in the long run. But if I were to read it, I wouldn't do it for the usefulness but rather because gathering knowledge and understanding is the right thing to do. There must be a million things that are more useful in the short term, and really reading TAOCP is bound to take years.
- userbinator 7y agoCongratulations Scott, you are one of the very few people to have Knuth make a comment on your blog. Printing out the comment and framing it on your wall may be very appropriate. ;-) (I know he gives out reward checks, but this is the first time I've seen such a comment. I wonder if anyone knows of any others.)
- Alissia17 7y agoRate my young hot ass, pls ---- https://ezo.no/kitty17 https://ezo.no/kitty17
- sjg007 7y agoDoes this have any implications for P vs NP? I guess the question would be is the sensitivity of a 3-SAT problem related to finding a solution?
- TrueCarry 7y agoI'm sorry, I still don't understand practical applications of that paper. Does that mean we now can write "smart" function with input of booleans and sensitivity and get results much faster than if we just iterate over booleans?
- JulianWasTaken 7y agoIt's not my field, so there actually may be practical applications, but in general mathematicians don't really care directly about applications (unless they do). The result stands on its own merit (and may either help in applications later, or simply as a beautiful result, or may later be useful in the proof of some dependent theorem that does have applications). But essentially a large part of why this is a big deal is that it was a "long"-unproven conjecture that smart people had looked at over the years and not solved, and expected to take heavier machinery, and that all of a sudden got a really simple proof.
- hoten 7y agono. math people just like to math.
- devnulloverflow 7y agoWhile I generally thing that looking for practical applications of research is nonsense, this one seems to be in an obviously useful area. It's all about different ways of measuring how good a function is at scrambling the input data. I'm guessing if you want to break (or make) a hash or cryptosystem you will use these measures over various aspects of it to look for weaknesses or some such. This particular proof seems to be saying that the measure called sensitivity will give you similar answer to a bunch of other measures. On the one hand, that's disappointing (a measure that gave totally different results might enlighten whole new ways of attacking/strengthening you crypto). On the other hand it is encouraging because if a whole bunch of very different measures agree, then that's a sign that they are on to something real.
- ryacko 7y agoI’d like to be corrected if I’m wrong, but this seems to be about arranging data to be better processed in quantum computing, to retrieve parity information. I wonder if this has application to McEliece codes, or future communications. I hope so.
- hoten 7y agowhat a legend. he's golfing.
- m463 7y agoAny proof can fit on one page. (for the set k where k is the inventor of tex)
- LegitShady 7y agoprove it on one page.
- svat 7y agoA few random comments: • Obviously, this is typeset with TeX. • Though originally Knuth created TeX for books rather than single-page articles, he's most familiar with this tool so it's unsurprising that he'd use it to just type something out. (I remember reading somewhere that Joel Spolsky, who was PM on Excel, used Excel for everything.) • To create the PDF, where most modern TeX users might just use pdftex, he seems to first created a DVI file with tex (see the PDF's title “huang.dvi”), then gone via dvips (version 5.98, from 2009) to convert to PostScript, then (perhaps on another computer?) “Acrobat Distiller 19.0 (Macintosh)” to go from PS to PDF. • If you find it different from the “typical” paper typeset with LaTeX, remember that Knuth doesn't use LaTeX; this is typeset in plain TeX. :-) Unlike LaTeX which aims to be a “document preparation system” with “logical”/“structured” (“semantic”) markup rather than visual formatting, for Knuth TeX is just a tool; typically he works with pencil and paper and uses a computer/TeX only for the final typesetting, where all he needs is to control the formatting. • Despite being typeset with TeX which is supposed to produce beautiful results, the document may appear very poor on your computer screen (at least it did when I first viewed it on a Linux desktop; on a Mac laptop with Retina display it looks much better though somewhat “light”). But if you zoom in quite a bit, or print it, it looks great. The reason is that Knuth uses bitmap (raster) fonts, not vector fonts like the rest of the world. Once bitten by “advances” in font technology (his original motivation to create TeX & METAFONT), he now prefers to use bitmap fonts and completely specify the appearance (when printed/viewed on a sufficiently high-resolution device anyway), rather than use vector fonts where the precise rasterization is up to the PDF viewer. • An extension of the same point: everything in his workflow is optimized for print, not onscreen rendering. For instance, the PDF title is left as “huang.dvi” (because no one can look at it when printed), the characters are not copyable, etc. (All these problems are fixable with TeX too these days.) • Note what Knuth has done here: he's taken a published paper, understood it well, thought hard about it, and come up with (what he feels is) the “best” way to present this result. This has been his primary activity all his life, with The Art of Computer Programming, etc. Every page of TAOCP is full of results from the research literature that Knuth has often understood better than even the original authors, and presented in a great and uniform style — those who say TAOCP is hard to read or boring(!) just have to compare against the original papers to understand Knuth's achievement. He's basically “digested” the entire literature, passed it through his personal interestingness filter, and presented it an engaging style with enthusiasm to explain and share. > when Knuth won the Kyoto Prize after TAOCP Volume 3, there was a faculty reception at Stanford. McCarthy congratulated Knuth and said, "You must have read 500 papers before writing it." Knuth answered, "Actually, it was 5,000." Ever since, I look at TAOCP and consider that each page is the witty and insightful synthesis of ten scholarly papers, with added Knuth insights and inventions. (https://blog.computationalcomplexity.org/2011/10/john-mccarthy-1927-2011.html?showComment=1319546990817#c6154784930906980717 https://blog.computationalcomplexity.org/2011/10/john-mccart...) • I remember a lunchtime conversation with some colleagues at work a few years ago, where the topic of the Turing Award came up. Someone mentioned that Knuth won the Turing Award for writing (3 volumes of) TAOCP, and the other person did not find it plausible, and said something like “The Turing Award is not given for writing textbooks; it's given for doing important research...” — but in fact Knuth did receive the award for writing TAOCP; writing and summarizing other people's work is his way of doing research, advancing the field by unifying many disparate ideas and extending them. When he invented the Knuth-Morris-Pratt algorithm in his mind he was “merely” applying Cook's theorem on automata to a special case, when he invented LR parsing he was “merely” summarizing various approaches he had collected for writing his book on compilers, etc. Even his recent volumes/fascicles of TAOCP are breaking new ground (e.g. currently simply trying to write about Dancing Links as well as he can, he's coming up with applying it to min-cost exact covers, etc. Sorry for long comment, got carried away :-)
- sunstone 7y agoOk so now you're just showing off. :)
- Procrastes 7y agoTalk about a coincidence. I just interviewed (for an article) someone today who happened to mention out of the blue that he's mentioned in the "Art of Computer Programming". He asked me if I "had heard of Donald Knuth." He didn't know if people still read those volumes. :) I let him know folks are very much still interested.
- pradn 7y agoIn what way is he mentioned? I'm curious.
- estomagordo 7y agoThis is amazing.
- cromwellian 7y agoI met Knuth a few months ago helping my wife do portrait photography of him (I got to hold lighting/reflectors :) ), and got to chat with him on machine learning and other research computer science results. I was floored at the sheer amount of papers and author names he could recall on the fly, he had already read every citation I had. At his age, his mind is as sharp as a tack, and watching him code and demo some stuff to me, he was incredibly adept in his programming environment, far more productive than I would be. I really hope he can finish all of the volumes of his books, it will truly be a gift to humanity.
- svat 7y agoThanks for sharing. That was great to hear, and like you I too hope for many more volumes coming out. Your comment reminded me of the following from Herbert Wilf, 2002: https://www.math.upenn.edu/~wilf/website/dek.pdf https://www.math.upenn.edu/~wilf/website/dek.pdf (which I believe even better after reading your comment): Here’s a little story of math at 35,000 feet. […] I wrote to Don and sent him a few more related results that Neil and I had gotten […]. As a result, I got a letter from him that I found to very moving indeed. Of course it was in his familiar pencilled scrawl, written at the bottom of the note that I had sent him. It began as follows: > > Dear Herb, I am writing this on an airplane while flying to Austin to celebrate Dijkstra’s 70th birthday. This whole subject is beautiful and still ripe for research (after more than 150 years of progress!), so I will tell you what I know about it (or can recall while on a plane) in hopes that it will be useful. > There followed four pages of tightly handwritten information that was a gold mine of the history of the sequence b(n) and related matters. It contained references to de Rham, Dijkstra, Carlitz, Neil Sloane, Stern (of Stern-Brocot trees fame), Eisenstein, Conway, Zagier, Schönhage, Hardy, Ramanujan, and so forth. It did not merely mention the names. It contained precise statements of the results of interest, of their relationship with the result of Calkin and myself and with each other. It contained a number of Don’s own observations about related questions, and had several conjectures, with background, to offer. > It was a letter, ladies and gentlemen, that was written by a man who very much loves his subject and the history of his subject, and who knows more about that than any five other human beings that you could name. His enthusiasm, his background knowledge, and his mathematical values, that impelled him to write such a letter under such conditions, can be taken as examples for the rest of us to aspire to.
- tw1010 7y agoThis is especially interesting to think about in light of the whole school of self-teaching Knuth has pushed out into the world in fragmented pieces here and there.
- utopcell 7y agoNot even a page: 1/3rd of it is notes!