<story><title>Knuth on Huang&apos;s Sensitivity Proof: “I&apos;ve got the proof down to one page” [pdf]</title><url>https://www.scottaaronson.com/blog/?p=4229#comment-1815290</url></story><parent_chain><item><author>svat</author><text>A few random comments:&lt;p&gt;• Obviously, this is typeset with TeX.&lt;p&gt;• Though originally Knuth created TeX for books rather than single-page articles, he&amp;#x27;s most familiar with this tool so it&amp;#x27;s unsurprising that he&amp;#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.)&lt;p&gt;• 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&amp;#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.&lt;p&gt;• If you find it different from the “typical” paper typeset with LaTeX, remember that Knuth doesn&amp;#x27;t use LaTeX; this is typeset in plain TeX. :-) Unlike LaTeX which aims to be a “document preparation system” with “logical”&amp;#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&amp;#x2F;TeX only for the final typesetting, where all he needs is to control the formatting.&lt;p&gt;• 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;amp; METAFONT), he now prefers to use bitmap fonts and completely specify the appearance (when printed&amp;#x2F;viewed on a sufficiently high-resolution device anyway), rather than use vector fonts where the precise rasterization is up to the PDF viewer.&lt;p&gt;• 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.)&lt;p&gt;• Note what Knuth has done here: he&amp;#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 &lt;i&gt;The Art of Computer Programming&lt;/i&gt;, 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&amp;#x27;s achievement. He&amp;#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.&lt;p&gt;&amp;gt; when Knuth won the Kyoto Prize after TAOCP Volume 3, there was a faculty reception at Stanford. McCarthy congratulated Knuth and said, &amp;quot;You must have read 500 papers before writing it.&amp;quot; Knuth answered, &amp;quot;Actually, it was 5,000.&amp;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.&lt;p&gt;(&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;blog.computationalcomplexity.org&amp;#x2F;2011&amp;#x2F;10&amp;#x2F;john-mccarthy-1927-2011.html?showComment=1319546990817#c6154784930906980717&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;blog.computationalcomplexity.org&amp;#x2F;2011&amp;#x2F;10&amp;#x2F;john-mccart...&lt;/a&gt;)&lt;p&gt;• 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&amp;#x27;s given for doing important research...” — but in fact Knuth did receive the award for writing TAOCP; writing and summarizing other people&amp;#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&amp;#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&amp;#x2F;fascicles of TAOCP are breaking new ground (e.g. currently simply trying to write about Dancing Links as well as he can, he&amp;#x27;s coming up with applying it to min-cost exact covers, etc.&lt;p&gt;Sorry for long comment, got carried away :-)</text></item></parent_chain><comment><author>svat</author><text>Looks like no one complained about the long comment, so some further trivia I omitted mentioning:&lt;p&gt;• The problem that one cannot copy text from a PDF created via dvips and using METAFONT-generated bitmap fonts has recently been fixed — the original author of dvips, Tomas Rokicki ([1], [2]) has “come out of retirement” (as far as this program is concerned anyway) to fix this and is giving a talk about it next week at the TeX Users Group conference ([3], [4]):&lt;p&gt;&amp;gt; Admittedly this is a rare path these days; most people are using pdfTeX or using Type 1 fonts with dvips, but at least one prominent user continues to use bitmap fonts.&lt;p&gt;So in the future (when&amp;#x2F;if Knuth upgrades!) his PDFs too will be searchable. :-)&lt;p&gt;• In some sense, even Knuth&amp;#x27;s work on TeX and METAFONT can be seen as an extension of his drive to understand and explain (in his own unique way) others&amp;#x27; work: at one point, suddenly having to worry about the appearance of his books, he took the time to learn intensively about typesetting and font design, then experiment and encode whatever he had learned into programs of production quality (given constraints of the time). This is in keeping with his philosophy: “Science is what we understand well enough to explain to a computer. Art is everything else we do.” and (paraphrasing from a few mentions like [5] and [6]) “The best way to understand something is to teach it &lt;i&gt;to a computer&lt;/i&gt;”.&lt;p&gt;• Finally returning (somewhat) to the topic, and looking at the 2&amp;#x2F;3rds-page proof that Knuth posted [7], one may ask, is it really any “better”, or “simpler”, than Huang&amp;#x27;s original proof [8]? After all, Huang&amp;#x27;s proof is already very short: just about a page and a half, for a major open problem for 30 years; see the recent Quanta article ([9], HN discussion [10]). And by using Cauchy’s Interlace Theorem, graph terminology, and eigenvalues, it puts the theorem in context and (to researchers in the field) a “natural” setting, compared to Knuth&amp;#x27;s proof that cuts through all that and keeps only the unavoidable bare essentials. This is a valid objection; my response to that would be: different readers are different, and there are surely some readers to whom a proof that does not even involve eigenvalues is really more accessible. A personal story: in grad school I “learned” the simplex algorithm for linear programming. Actually I never quite learned it, and couldn&amp;#x27;t answer basic questions about it. Then more recently I discovered Knuth&amp;#x27;s “literate program” implementing and explaining the simplex algorithm [11], and that one I understood much better.&lt;p&gt;&amp;gt; The famous simplex procedure is subtle yet not difficult to fathom, even when we are careful to avoid infinite loops. But I always tend to forget the details a short time after seeing them explained in a book. Therefore I will try here to present the algorithm in my own favorite way—which tends to be algebraic and combinatoric rather than geometric—in hopes that the ideas will then be forever memorable, at least in my own mind.&lt;p&gt;I can relate: although the simplex algorithm has an elegant geometrical interpretation about what happens when it does pivoting etc., and this is the way one “ought” to think about it, somehow I am more comfortable with symbol-pushing, having an underdeveloped intuition for geometry and better intuition for computational processes (algorithms). Reading Knuth&amp;#x27;s exposition, which may seem pointless to someone more comfortable with the geometrical presentation, “clicked” for me in a way nothing had before.&lt;p&gt;This is one reason I am so fascinated by the work of Don Knuth: though I cannot hope to compare myself in either ability (even his exploits as a college kid are legendary [12]) or productivity or taste, I &lt;i&gt;can&lt;/i&gt; relate to some of his aesthetic preferences such as for certain areas&amp;#x2F;styles of mathematics&amp;#x2F;programming over others, and being able to so well “relate” to someone this way gives you hope that maybe by adopting some of the same habits that worked for them (e.g.: somewhere, Knuth mentions that tries to start every day by doing whichever thing he&amp;#x27;s been dreading the most), you&amp;#x27;ll be able to move a few steps in somewhat the same direction, and if nothing else, this puts me in mind of what Bhavabhuti said many centuries ago [13] about finding someone with the same spirit, so to speak.&lt;p&gt;[1]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;tomas.rokicki.com&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;tomas.rokicki.com&lt;/a&gt;
[2]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.maa.org&amp;#x2F;sites&amp;#x2F;default&amp;#x2F;files&amp;#x2F;pdf&amp;#x2F;upload_library&amp;#x2F;2&amp;#x2F;Joyner-CMJ-2015.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.maa.org&amp;#x2F;sites&amp;#x2F;default&amp;#x2F;files&amp;#x2F;pdf&amp;#x2F;upload_library&amp;#x2F;2...&lt;/a&gt;
[3]: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;tug.org&amp;#x2F;tug2019&amp;#x2F;preprints&amp;#x2F;rokicki-pdfbitmap.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;tug.org&amp;#x2F;tug2019&amp;#x2F;preprints&amp;#x2F;rokicki-pdfbitmap.pdf&lt;/a&gt;
[4]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;rokicki&amp;#x2F;type3search&amp;#x2F;blob&amp;#x2F;a70b5f3&amp;#x2F;README.md#introduction&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;rokicki&amp;#x2F;type3search&amp;#x2F;blob&amp;#x2F;a70b5f3&amp;#x2F;README.m...&lt;/a&gt;
[5]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.maa.org&amp;#x2F;sites&amp;#x2F;default&amp;#x2F;files&amp;#x2F;pdf&amp;#x2F;upload_library&amp;#x2F;22&amp;#x2F;Ford&amp;#x2F;DonaldKnuth.pdf#page=5&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.maa.org&amp;#x2F;sites&amp;#x2F;default&amp;#x2F;files&amp;#x2F;pdf&amp;#x2F;upload_library&amp;#x2F;2...&lt;/a&gt;
[6]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;youtu.be&amp;#x2F;eDs4mRPJonU?t=1514&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;youtu.be&amp;#x2F;eDs4mRPJonU?t=1514&lt;/a&gt; (25:14 to 26:46)
[7]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.cs.stanford.edu&amp;#x2F;~knuth&amp;#x2F;papers&amp;#x2F;huang.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.cs.stanford.edu&amp;#x2F;~knuth&amp;#x2F;papers&amp;#x2F;huang.pdf&lt;/a&gt;
[8]: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;www.mathcs.emory.edu&amp;#x2F;~hhuan30&amp;#x2F;papers&amp;#x2F;sensitivity_1.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.mathcs.emory.edu&amp;#x2F;~hhuan30&amp;#x2F;papers&amp;#x2F;sensitivity_1.pd...&lt;/a&gt;
[9]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.quantamagazine.org&amp;#x2F;mathematician-solves-computer-science-conjecture-in-two-pages-20190725&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.quantamagazine.org&amp;#x2F;mathematician-solves-computer...&lt;/a&gt;
[10]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;news.ycombinator.com&amp;#x2F;item?id=20531987&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;news.ycombinator.com&amp;#x2F;item?id=20531987&lt;/a&gt;
[11]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;shreevatsa&amp;#x2F;knuth-literate-programs&amp;#x2F;blob&amp;#x2F;9b46afe&amp;#x2F;programs&amp;#x2F;lp.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;shreevatsa&amp;#x2F;knuth-literate-programs&amp;#x2F;blob&amp;#x2F;9...&lt;/a&gt;
[12]: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;ed-thelen.org&amp;#x2F;comp-hist&amp;#x2F;B5000-AlgolRWaychoff.html#7&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;ed-thelen.org&amp;#x2F;comp-hist&amp;#x2F;B5000-AlgolRWaychoff.html#7&lt;/a&gt;
[13]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;shreevatsa.wordpress.com&amp;#x2F;2015&amp;#x2F;06&amp;#x2F;16&amp;#x2F;bhavabhuti-on-finding-a-reader&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;shreevatsa.wordpress.com&amp;#x2F;2015&amp;#x2F;06&amp;#x2F;16&amp;#x2F;bhavabhuti-on-fi...&lt;/a&gt;</text></comment>
<story><title>Knuth on Huang&apos;s Sensitivity Proof: “I&apos;ve got the proof down to one page” [pdf]</title><url>https://www.scottaaronson.com/blog/?p=4229#comment-1815290</url></story><parent_chain><item><author>svat</author><text>A few random comments:&lt;p&gt;• Obviously, this is typeset with TeX.&lt;p&gt;• Though originally Knuth created TeX for books rather than single-page articles, he&amp;#x27;s most familiar with this tool so it&amp;#x27;s unsurprising that he&amp;#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.)&lt;p&gt;• 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&amp;#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.&lt;p&gt;• If you find it different from the “typical” paper typeset with LaTeX, remember that Knuth doesn&amp;#x27;t use LaTeX; this is typeset in plain TeX. :-) Unlike LaTeX which aims to be a “document preparation system” with “logical”&amp;#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&amp;#x2F;TeX only for the final typesetting, where all he needs is to control the formatting.&lt;p&gt;• 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;amp; METAFONT), he now prefers to use bitmap fonts and completely specify the appearance (when printed&amp;#x2F;viewed on a sufficiently high-resolution device anyway), rather than use vector fonts where the precise rasterization is up to the PDF viewer.&lt;p&gt;• 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.)&lt;p&gt;• Note what Knuth has done here: he&amp;#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 &lt;i&gt;The Art of Computer Programming&lt;/i&gt;, 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&amp;#x27;s achievement. He&amp;#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.&lt;p&gt;&amp;gt; when Knuth won the Kyoto Prize after TAOCP Volume 3, there was a faculty reception at Stanford. McCarthy congratulated Knuth and said, &amp;quot;You must have read 500 papers before writing it.&amp;quot; Knuth answered, &amp;quot;Actually, it was 5,000.&amp;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.&lt;p&gt;(&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;blog.computationalcomplexity.org&amp;#x2F;2011&amp;#x2F;10&amp;#x2F;john-mccarthy-1927-2011.html?showComment=1319546990817#c6154784930906980717&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;blog.computationalcomplexity.org&amp;#x2F;2011&amp;#x2F;10&amp;#x2F;john-mccart...&lt;/a&gt;)&lt;p&gt;• 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&amp;#x27;s given for doing important research...” — but in fact Knuth did receive the award for writing TAOCP; writing and summarizing other people&amp;#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&amp;#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&amp;#x2F;fascicles of TAOCP are breaking new ground (e.g. currently simply trying to write about Dancing Links as well as he can, he&amp;#x27;s coming up with applying it to min-cost exact covers, etc.&lt;p&gt;Sorry for long comment, got carried away :-)</text></item></parent_chain><comment><author>anaphor</author><text>I feel like he also deserves recognition for his awesome lectures (which are generally pretty low-tech but amazingly well thought out).&lt;p&gt;E.g. all of his &amp;quot;christmas tree lectures&amp;quot; are available on youtube from Stanford &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.youtube.com&amp;#x2F;watch?v=_cR9zDlvP88&amp;amp;list=PLoROMvodv4rOAvKVR_dyCigSBMcYjevYB&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.youtube.com&amp;#x2F;watch?v=_cR9zDlvP88&amp;amp;list=PLoROMvodv4...&lt;/a&gt;</text></comment>