TE
TechEcho
Home24h TopNewestBestAskShowJobs
GitHubTwitter
Home

TechEcho

A tech news platform built with Next.js, providing global tech news and discussions.

GitHubTwitter

Home

HomeNewestBestAskShowJobs

Resources

HackerNews APIOriginal HackerNewsNext.js

© 2025 TechEcho. All rights reserved.

Knuth on Huang's Sensitivity Proof: “I've got the proof down to one page” [pdf]

462 pointsby espeedalmost 6 years ago

20 comments

svatalmost 6 years ago
A few random comments:<p>• Obviously, this is typeset with TeX.<p>• Though originally Knuth created TeX for books rather than single-page articles, he&#x27;s most familiar with this tool so it&#x27;s unsurprising that he&#x27;d use it to just type something out. (I remember reading somewhere that Joel Spolsky, who was PM on Excel, used Excel for everything.)<p>• 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&#x27;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.<p>• If you find it different from the “typical” paper typeset with LaTeX, remember that Knuth doesn&#x27;t use LaTeX; this is typeset in plain TeX. :-) Unlike LaTeX which aims to be a “document preparation system” with “logical”&#x2F;“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&#x2F;TeX only for the final typesetting, where all he needs is to control the formatting.<p>• 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 &amp; METAFONT), he now prefers to use bitmap fonts and completely specify the appearance (when printed&#x2F;viewed on a sufficiently high-resolution device anyway), rather than use vector fonts where the precise rasterization is up to the PDF viewer.<p>• 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.)<p>• Note what Knuth has done here: he&#x27;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 <i>The Art of Computer Programming</i>, 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&#x27;s achievement. He&#x27;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.<p>&gt; when Knuth won the Kyoto Prize after TAOCP Volume 3, there was a faculty reception at Stanford. McCarthy congratulated Knuth and said, &quot;You must have read 500 papers before writing it.&quot; Knuth answered, &quot;Actually, it was 5,000.&quot; 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.<p>(<a href="https:&#x2F;&#x2F;blog.computationalcomplexity.org&#x2F;2011&#x2F;10&#x2F;john-mccarthy-1927-2011.html?showComment=1319546990817#c6154784930906980717" rel="nofollow">https:&#x2F;&#x2F;blog.computationalcomplexity.org&#x2F;2011&#x2F;10&#x2F;john-mccart...</a>)<p>• 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&#x27;s given for doing important research...” — but in fact Knuth did receive the award for writing TAOCP; writing and summarizing other people&#x27;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&#x27;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&#x2F;fascicles of TAOCP are breaking new ground (e.g. currently simply trying to write about Dancing Links as well as he can, he&#x27;s coming up with applying it to min-cost exact covers, etc.<p>Sorry for long comment, got carried away :-)
评论 #20591618 未加载
评论 #20590984 未加载
评论 #20591274 未加载
评论 #20590892 未加载
评论 #20592308 未加载
评论 #20591457 未加载
评论 #20593695 未加载
评论 #20590726 未加载
评论 #20591599 未加载
评论 #20590986 未加载
评论 #20594286 未加载
cromwellianalmost 6 years ago
I met Knuth a few months ago helping my wife do portrait photography of him (I got to hold lighting&#x2F;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.
评论 #20591715 未加载
评论 #20591721 未加载
评论 #20592368 未加载
评论 #20593707 未加载
userbinatoralmost 6 years ago
Congratulations Scott, you are one of the <i>very</i> few people to have <i>Knuth</i> make a comment on your blog. Printing out the comment and framing it on your wall may be very appropriate. ;-)<p>(I know he gives out reward checks, but this is the first time I&#x27;ve seen such a comment. I wonder if anyone knows of any others.)
评论 #20592502 未加载
zcbenzalmost 6 years ago
Huang&#x27;s comment is also very interesting:<p>&gt; Regarding how long it took me to find this proof, here is the timeline for those who are interested.<p><a href="https:&#x2F;&#x2F;www.scottaaronson.com&#x2F;blog&#x2F;?p=4229#comment-1813116" rel="nofollow">https:&#x2F;&#x2F;www.scottaaronson.com&#x2F;blog&#x2F;?p=4229#comment-1813116</a>
评论 #20590344 未加载
评论 #20590842 未加载
评论 #20590116 未加载
espeedalmost 6 years ago
NB: Proof announcement thread from a few weeks ago...<p>Sensitivity Conjecture Resolved <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=20338281" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=20338281</a>
Procrastesalmost 6 years ago
Talk about a coincidence. I just interviewed (for an article) someone today who happened to mention out of the blue that he&#x27;s mentioned in the &quot;Art of Computer Programming&quot;. He asked me if I &quot;had heard of Donald Knuth.&quot; He didn&#x27;t know if people still read those volumes. :) I let him know folks are very much still interested.
评论 #20607057 未加载
quxbaralmost 6 years ago
:&#x27;) it&#x27;s like watching a really great game of baseball
评论 #20589989 未加载
AnimalMuppetalmost 6 years ago
More like two thirds of a page - the bottom third is &quot;notes&quot; which are not really part of the proof!
评论 #20589862 未加载
tw1010almost 6 years ago
This 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.
utopcellalmost 6 years ago
Not even a page: 1&#x2F;3rd of it is notes!
评论 #20593203 未加载
doe88almost 6 years ago
One thing is certain reading a mathematical proof from Knuth is TeX and its beauty will be used ;)
评论 #20589835 未加载
TrueCarryalmost 6 years ago
I&#x27;m sorry, I still don&#x27;t understand practical applications of that paper. Does that mean we now can write &quot;smart&quot; function with input of booleans and sensitivity and get results much faster than if we just iterate over booleans?
评论 #20590497 未加载
评论 #20590628 未加载
评论 #20590414 未加载
评论 #20590576 未加载
评论 #20590420 未加载
oneepicalmost 6 years ago
<i>The Don.</i> Quite a fast turnaround too.
评论 #20590276 未加载
hotenalmost 6 years ago
what a legend. he&#x27;s golfing.
estomagordoalmost 6 years ago
This is amazing.
dangalmost 6 years ago
We changed the URL from <a href="https:&#x2F;&#x2F;www.cs.stanford.edu&#x2F;~knuth&#x2F;papers&#x2F;huang.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.stanford.edu&#x2F;~knuth&#x2F;papers&#x2F;huang.pdf</a> to where Knuth actually said that.
emmelaichalmost 6 years ago
Not a link to a pdf, despite the HN title.<p>It&#x27;s a link to Knuth&#x27;s comment which has a link to the pdf.<p>[edit; saw dang&#x27;s comment just now which says the HN link has changed.]
评论 #20590403 未加载
sunstonealmost 6 years ago
Ok so now you&#x27;re just showing off. :)
m463almost 6 years ago
Any proof can fit on one page.<p>(for the set k where k is the inventor of tex)
评论 #20590609 未加载
sjg007almost 6 years ago
Does 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?