Donald Knuth: Algorithms, Complexity, Life, and the Art of Programming [video] | Hacker News Reader

Donald Knuth: Algorithms, Complexity, Life, and the Art of Programming [video]

youtube.com

355 pointstambourine_man72 comments

This is the conversation between Lex Fridman (MIT) and Donald Knuth, the legendary computer scientist & mathematician. Lex Fridman's podcast is my favorite and it's about Artificial General Intelligence (AGI). He says: "To me AI is bigger than computing, it is our civilization's journey into understanding the human mind and creating echoes of it in the machine.".

Yup. Lex’s interviewing style is like how I would do it. He’s a gem and I’m so glad he is doing this podcast.

Link to podcast for the lazy https://lexfridman.com/ai/.

Looks good, thanks for sharing! I've had a hard time finding podcasts that have a conversational style that I enjoy; so far I like only https://softwareengineeringdaily.com/, but this one looks really promising.

I recommend Mindscape by Sean Carroll. https://www.preposterousuniverse.com/podcast

I found Lex's podcast a few months ago after hearing his George Hotz interview. It's now become my favourite podcast. I really like the mix of technical and philosophical questions, often about the future of humanity.

Thoughts on CoRecursive? It's a conversational interview podcast that I like about topics that are relevant.

I don't know Lex Fridman, but with all respect, I don't like him as an interviewer at all. He has zero interviewing experience, IMHO. It looks so amateur. Regardless, kudos to him for bringing in so many amazing people. His playlist is sick!

You need to watch three of them. He has a style and once it “clicks”, it’s rather interesting.

I had a similar impression months ago, and after listening to a few - I was so happy I gave it a fair chance.

Hmm, I find your observation interesting, but I don’t really understand it. Can you explain or give examples of why you think he is not experienced?

I always thought of his podcast as conversations, not interviews. Maybe that’s why it always worked fine for me.

I think your post is valuable opinion and feeding discussion so have an upvote to balance the downvoters. (why did they..? oh well :shrug:)

I actually disagree with you on interview style, I like his (it grows on you, or so I found); his playlist is indeed sick. And it keeps getting better, I suspect he'll eventually get 80% of the who's-who in AI or around it. Probably the most promising high-level podcast about it.

Other podcasts are more in the weeds, actual work on ML/DL etc, production cases and frameworks (see The Changelog's master feed for instance, "Practical AI" with actual SWE's). Lex's is interesting insofar as he's an AI researcher at MIT, the highest technical acumen you can reach in the field, so you can trust him to orient/frame the conversation (actually, learn from his follow-up questions and remarks). And it's sometimes funny (when you have some background too) to see/hear his responses to non-technical interviewees.

He's a great mind (and has a great heart), no question about it; thus whatever quirks you may find diverging from classic interview style are worth ignoring. Focus on the meat, when it gets good, it gets really good.

Thank you. I posted a comment this morning and had a chance to look through Fridman's YouTube channel before replying to other commenters.

I didn't know that these interviews are podcast-first, which is probably why the interviewer is so laid back and slow talking, as pointed out by @unoti. I looked up Fridman's lectures, they are indeed a little bit more energetic, but he is generally a calm individual, so in combination with slow talking and monotone voice that he intentionally uses in podcasts, it makes his questions quite boring to listen, which is what was immediately reflected in my original comment.

> thus whatever quirks you may find diverging from classic interview style are worth ignoring. Focus on the meat, when it gets good, it gets really good.

Lex Fridman is smart. No doubt. If one listens carefully, he indeed asks good questions, which is something I originally missed. He interviews great people and the meat is obviously there. But I still strongly believe that there is a huge room for improvement for Lex as an interviewer and content creator. Has he interviewed unknown people, nobody would listen to him, IMHO.

Ah, I see. I think, in all fairness to him, you express a desire for some 'journalistic' or 'interviewer' skills. I totally understand that, the greats in those fields are awesome.

However I think it's a tall order to ask people in general to excel in two entirely distinct domains, especially at such a 'young' age (MIT must've taken most of his time so far). So with domain-driven people who dabble in media, we get their strong vertical at the cost of more mediocre delivery — but to me that remains sweeter than a "professional" journalist who speaks second-hand about everything, at least for most technical or complex topics.

He's got time to get a lot better at interviewing, podcasting, if that's the goal. Eventually, he can be both a great AI researcher and a great podcaster. Meanwhile, I'll take it regardless because that's the best we've got now.

> Has he interviewed unknown people, nobody would listen to him, IMHO.

If the topic were totally irrelevant, maybe; but I have a fondness for scientists trying to speak to everyone, e.g. on YouTube / podcast / whatever, so I would still listen probably. Like that guy, Robert Miles from Cambridge who speaks of AI safety[1] — delivery wasn't great in the beginning, but damn were the topics incredible food for thought.

[1]: https://www.youtube.com/channel/UCLB7AzTwc6VFZrBsO2ucBMg

interestingly, I found this podcast about 6 months ago and it has quickly become one of my three must-listen channels. He has some amazing guests and conversations and I find his questions thoughtful and wide-ranging, leading to some really interesting perspectives outside of the expected domain of the guest. For this episode I finally looked up the YouTube feed and thought, "that's not at all how I pictured him! he's wearing a suit and tie?". I wonder how much the visual medium changes the impression for a first-time listener (not that either format put me off personally).

I agree, he's really difficult to listen to. It's surprising how someone with communication skills as bad as his managed to get quite a few great guests.

I had the opposite reaction. I thought Fridman was a very good interviewer. I've talked with Donald Knuth a half dozen times over the last thirty years. I really enjoyed this interview. Knuth seemed relaxed and to be having a good time thinking about the questions and answering them. If Knuth is happy, I'm happy.

Lex has a distinctive style of interviewing. He's intentionally laid back and talks slowly, and gives his guests lots of room to be the star. But he's actually a dynamic and interesting speaker and quite knowledgeable; you can tell by watching some of his lectures (he's an MIT professor). He dumbs down his questions to give opportunity to his guests to explain their topics in their own way and to appeal to a broader audience.

But having said all that, one youtube commenter said of Lex's interview with Elon Musk that it was "two robots conversing without human supervision," which Lex brought up in a later interview with Elon and thought was pretty funny.

Just a correction, he is not a professor - he is a research scientists who sometimes puts together and lectures in short classes (MIT has this weird 1 month quarter thing that has a bunch of optional classes). Or so it was when I last checked.

Pretty much. IAP (Independent Activities Period). He's doing a Deep Learning series this month.

What do you dislike about his interview ? He asks good questions and listens. What more do you expect ?

>I don't know Lex Fridman, but with all respect, I don't like him as an interviewer at all. He has zero interviewing experience, IMHO. It looks so amateur.

Actually, this looks like 100% old-style quality interview.

People are not used to this style today, but it was the quintessential style before the 90s or so, and it's much deeper than the kind of shallow interviewing we see today from "pros" (including TV hacks like Charlie Rose).

Charlie Rose always seemed to be trying to play some sort of mind game to goad information out of his guests. I went down a rabbit hole of watching old historical interviews and discovered interviews were very tame. Like, Dick Cavett's famous interview with Marlon Brando - https://www.youtube.com/watch?v=uU-4wmwc2Rw where the host was friendly and letting the guest speak above all else. Anything resembling this level of genuine conversation is a nice treat.

Speaking about Knuth audiofiles/podcasts, I recently created a RSS feed for the Knuth's "Things a Computer Scientist Rarely Talks About" audio files (https://j11g.com/knuth.xml).

This way you can listen to it in your favorite podcast player.

For example, I added the feed to Overcast: https://overcast.fm/p1120847-YM0aS7

Thanks for this. I've just subscribed.

The Web of Stories interview from the late 1990s is also good:

https://www.youtube.com/playlist?list=PLVV0r6CmEsFzeNLngr1Jq...

Man do I wish I knew about something like this on Android

Loving the video. I have a couple of volumes of TAOCP. Even though I am not in CS, the series is so well known and so respected that it is a must-have. I'll periodically leaf through some pages and have a hard time grasping how much work he must have put in, how many papers he must have read - good, bad, and indifferent - to extract the best and put them all in context. No wonder he gave up email before most people even heard of it and decades before it became cool. I saw him many times on the Stanford campus in the late 1980s when I was a grad student in chemistry. Never went up to say hello and to thank him for TeX.

I think he has a secretary that does emails for him. Also he responded to my email a few years ago.

That's quite an accomplishment. I hear that people who get a reward check from him for errata or other help usually frame them instead of cashing them.

According to this, he has a secretary that filters messages for him: https://www-cs-faculty.stanford.edu/~knuth/email.html

Don't be too impressed, I didn't get a cheque. He's just a really nice guy.

FYI, he stopped sending checks back in 2008 due to check fraud: https://en.wikipedia.org/wiki/Knuth_reward_check. It's a shame. I had a professor that had received one for finding a bug somewhere and he proudly displayed it in his office. It was a pretty good conversation starter.

He still sends paper checks, issued by a fictitious Bank of San Serriffe, so you still have something to frame, in addition to being listed at https://www-cs-faculty.stanford.edu/~knuth/boss.html

Ahh, thanks for clarifying. I knew about the fictitious bank, but didn't realize you got a paper check for it.

Lockheed's legendary Kelly Johnson was said to have given quarters to anyone at the Skunkworks who won a technical bet off of him. I believe these were also treasured by those who got them.

And, at least in my case, he included a comic strip of a guy cashing a cheque at the bank, being asked by the bank teller what he got this cheque for. "Three dollars? You sure work cheap!".

I found that hilarious.

Knuth thinks machine learners are not geeks. What do you guys think.

Also he defines geek as people having certain qualities like understanding systems at different levels of abstraction.

> Knuth thinks machine learners are not geeks

I don't like games of telephone. Do you have a particular point in the video where Knuth says this? It will help to hear what Knuth says with his argument before I make a counterpoint (or maybe even agree with him).

26:14

I think it is unfair to apply:

> Also he defines geek as people having certain qualities like understanding systems at different levels of abstraction.

Knuth said this around the 7-minute mark. Nearly 20-minutes earlier than the machine-learning question. The discussion moved on, and I'm not entirely sure the two parts you bring up are related at all.

Does it matter?

Does anything matter?

Yes

Only for a semi-certain range of values of t, as far as I can tell. /s

I'm sure you guys have a wonderful proof but it doesn't fit in a comment.

IMO he's saying ML people are fundamentally scientists, and scientists care more about the data than the techniques; an applied machine learning expert is in some ways a domain empiricist. A geek perhaps is somebody who enjoys tinkering with systems and methods in and of itself.

Naturally there is some intersection, but these are all soft terms anyway. IMO geeks have lost overall everywhere, replaced by mainstream commercial interests because the tech world needed to grow very fast.

I agree with you. Just about the best 'proofs' I get in social-chaotic topics like this is by going to the extremes:

- a "total" or "100%" data scientist researching ML might spend the better part of his days in an office, without a computer, just thinking on a whiteboard and paper. He then hands specs for tech people to translate, implement, run (code, systems, workflow).

- "geek" means passionate (early 20th century word to describe "bookworms"), thus it may apply to anything — nowadays it's applied implicitly, without specifying further, to technology, "geek" means "tech geek". In that sense, whatever they do, geeks are never far from machines, gadgets, supercomputers (!?), some ethernet patch...

Both actually have nothing to do with each other, and do not seem mutually exclusive to me; but in the extreme range of the spectrum, they clearly are totally different people with unrelated concerns and, most likely, jobs.

But that's all fluff and you have to thank idling geeks for writing such blabla. (though I hear HR loves that kind of reports, profiling makes the world so easy, right? Hey, what do you know, someone somewhere might copy/paste these threads for a living as we speak).

This also reflects in Von Karman's saying: Scientists discover the world that exists, engineers create the world that never was.

He mentions (and shows) a favorite paper tablet he uses with very finely ruled lines. He found it in Canada about 40 years ago while visiting his sister. Anybody know who makes his tablets? discussion here: https://youtu.be/2BdBfsXbST8?t=2587

For those curious about the game of Hex mentioned at(59:35)

https://www.youtube.com/watch?list=PLrAXtmErZgOdP_8GztsuKi9n...

There is a John Nash connection:

https://en.wikipedia.org/wiki/Hex_(board_game)

You gotta love Donald Knuth. What a guy. And what a project TAOCP has turned into. I just hope like crazy that he actually finishes it. I hate to even entertain the possibility but Robert Jordan's name comes to mind right now. Sadly, Knuth is not a young man, and there appears to be a lot of material left to write.

Not only is there a lot of material left to write, Knuth is the greatest Yak Shaver in history: when he realized that the typography available for his next volume was substandard, he put off writing it for 30 years to revolutionize typography (not that I'm complaining!) Then when he picked it up, he realized his bespoke assembler language was out of date so he invented a new one first. He did finally get around to publishing part of another volume, though.

Actually this is only partly true.

Here's a compressed timeline of books and other works of Knuth:

1962: Starts writing TAOCP. 1968, 1969, 1973: Volume 1, 1st edition. 1969: Volume 2, 1st edition. 1973: Volume 3, 1st edition. 1974: Turing Award. 1974: Volume 1, 2nd edition. 1974: Surreal Numbers (written in 6 days “and on the 7th day he rested”). 1976: Mariages Stables et leurs relations avec d'autres problèmes combinatoires.

1977 February: Receives galley of Volume 2 2nd edition (publishers have switched from hot-metal typesetting (Monotype) to phototypesetting, is dissatisfied with typography and excited by the possibility of getting it right with digital typesetting). Plans to have galleys ready in the summer :-) 1978 January: Gives Gibbs lecture (“Mathematical Typography”) on his ongoing research, unexpectedly many people are excited and want to use TeX. 1978: Finishes first version of TeX (aka TeX78, in SAIL) 1980: Starts work on rewrite of TeX (so that it can be used outside SAIL). 1981: Mathematics for the Analysis of Algorithms. 1981: Volume 2, 2nd edition. Realizes fonts still look bad on paper, starts getting more font design feedback from the masters. 1982: Finishes TeX, starts rewrite of METAFONT. 1984: Finishes METAFONT.

1986: Volumes ABCDE of Computers and Typesetting 1990: Announces end of his work on TeX and METAFONT (will only fix major bugs; others can continue writing other programs)

1992, 1996, 1999, 2000, 2003, 2003, 2010, 2011, 2011: Eight (plus one) volumes of collected papers.

1989: Mathematical Writing (lecture notes) 1990: 3:16 Bible Texts Illuminated (stratified random sampling of the Bible, with illustrations by many designers). 1992: Axioms and Hulls. 1993: CWEB. 1993: The Stanford GraphBase (some toy programs in CWEB). 1994: Concrete Mathematics.

1997: Volume 1, 3rd edition 1997: Volume 2, 3rd edition 1998: Volume 3, 3rd edition 1999: MMIXware

2001: Things a Computer Scientist Rarely Talks About (based on 1999 lectures at MIT on religion)

2005: Volume 4 Fasc 2 (part of Volume 4A later) 2005: Volume 4 Fasc 3 (part of Volume 4A later) 2006: Volume 4 Fasc 4 (part of Volume 4A later) 2008: Volume 4 Fasc 0 (part of Volume 4A later) 2009: Volume 4 Fasc 1 (part of Volume 4A later) 2011: Volume 4A.

2015: Volume 4, Fasc 6 (middle third of Volume 4B) 2018: Fantasia Apocalyptica Illustrated 2019/2020: Volume 4, Fasc 5 (first third of Volume 4B)

Planned: ????: Volume 4, Fasc 7 and 8 (last third of Volume 4B) 2025 (yeah right): Volume 5

So although he definitely badly underestimated how much time the typography project would take (he thought it would be done in a summer! then again, he also thought in 1962 that he'd be done with TAOCP in a year or two), and although it's technically correct that 38 years passed between 1973 (1st edition of Volume 3) and 2011 (Volume 4A), he wasn't spending all of it on typography; much of it was spent on other projects and on producing new editions (which in his case are a lot of work!) of earlier TAOCP volumes and other books. And even during the period 1977-1989 when he was working primarily on typography, he somehow managed to publish about 50 papers (P77 to P125), 60 other papers (Q48 to Q110), and 20 reports (R35 to R55): https://cs.stanford.edu/~knuth/vita.pdf (I really wish someone would parse his vita.tex from https://cs.stanford.edu/~knuth/vita.html, make it machine-readable and put it on a nice webpage sortable by year and topic and listing newer editions etc).

"Kuh-nooth"? The K isn't silent? Have I been saying it wrong all these years?

Yes, yes, and yes. It's in his FAQ: https://www-cs-faculty.stanford.edu/~knuth/faq.html

's what I get for being a recluse. I really have to get out more often.

I've always pronounced the K, I'm amazed if it turns out I've been saying it right all these years.

Is there a text transcript of this interview?

You could try to download the auto generated subtitles with youtube-dl.

Sure, but I'm just surprised that such a high-level interview is not available in a curated textual form, sanctioned by the interviewer.

You can give money via patreon to support this effort.

Or better yet, do it oneself: about 70 episodes, 7 billion people and change, it only takes 1 out of 100 million of us to transcribe 1 episode each to clear the work.

Hint: on a desktop browser, beneath the video you may click the "..." menu, select "Open transcript" and voila, you may copy/paste the whole (though UX is awful, I have yet to find a "copy all" button).

Here's a pastebin with minimal formatting for your perusal: https://pastebin.com/RQYhREEc

In the olden days, it was a journalist's job to transcribe their interviews, instead of publishing the raw unedited tapes of the recorded stuff.

It was usually a typist's job, and you paid for the newspaper, instead of watching the interview for free on Youtube.

What would be curated about an interview transcription?

Anyone knows which are the four Japanese people he mentiones expanding on his idea, then him finding out about it, generalizing it even more, writing code and playing around with it and then writing the final report? He was being really non-specific about the problem.

I'm interested in his writings now when he is no longer actively publishing research.

For example, that latest proof golf https://www.scottaaronson.com/blog/?p=4229#comment-1815290 was such a joy to read.

He is still actively publishing! TAOCP Vol 4 Fascicle 5 (which is going to be the first one-third of Volume 4B) came out less than a month ago, and it contains a lot of material and ideas that have never been published anywhere before. To answer your specific question, I'm positive he's referring to Dancing Links: see section 7.2.2.1 in the published fascicle, or his draft (pre-fascicle 5c) at https://cs.stanford.edu/~knuth/fasc5c.ps.gz -- the idea originally came from Hirosi Hitotumatu and Kohei Noshita (1979), then Knuth popularized it under the name "Dancing Links" (2000?), then the idea of "Dancing with ZDDs" was by Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata (2017), and he's extended it to Algorithm Z in this publication.

Thank you very much.

I've already read more than 50 pages and I love it. It's just incredible how much problems can be now solved by a faster algorithm.

I had an idea of solving lotto design problems, this might be a way to do it quickly.

Did Dr. Knuth stopped giving the Christmas Tree lecture this last year?

Is the Fridman interview the replacement?

No, no. The Christmas lecture happened this year as well (the 25th year in fact!): https://www.youtube.com/watch?v=3DKo219ZHMw&feature=emb_titl...

As is usual from Prof. Knuth, it's great with tonnes of nuggets of wisdom, especially if you are a fan of easter eggs (though his "style" of presentation bothers quite a few of my friends)! :)

It happened this year and it was packed. So much so that when I reached 10 min late, there were so many people (standing) that I couldn't actually see Knuth even though I was technically inside the Nvidia auditorium, Stanford. Could only see the overhead screen. Tried standing on my toes and kept craning my neck to no avail, so had to leave disappointed :-(

PS: I did get to attend and see him last year so that's something.

His answer to the last question is great. ;)

I am curious, what is his chair he talks about?

All he says is "I found this chair that was designed by a Swedish guy". Its black and looks like leather with a high cushioned back. That isn't a lot to go on. I searched and it doesn't seem to be something he has talked about before either.

I was interested too, but to be honest, its probably pretty unlikely that the perfect chair for Knuth is the perfect chair for me or you too.

Reply on news.ycombinator.com