3 ms·
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 p
by superpermutat0r 7y ago
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 https://www.scottaaronson.com/blog/?p=4229#comment-1815290 was such a joy to read.
- svat 7y agoHe 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 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.
- superpermutat0r 7y agoThank 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.