2 ms·

I read about how Bill Gates made a significant contribution to the pancake sorting problem in 1979 (iirc). Apparently, his results were bleeding edge for some

by Verdex 4y ago

I read about how Bill Gates made a significant contribution to the pancake sorting problem in 1979 (iirc). Apparently, his results were bleeding edge for something like 30 years until someone managed to get a result that was slightly better (~1%). A result that was accomplished with a lot of computer assistance. So, also exceptional in terms of wetware.

oska 4y ago
I strongly doubt that Gates made any significant contributions to computer science. So I'd appreciate a source to what you've claimed here. Gates had a 'genius' for ruthlessly exploiting a monopoly in business; apart from that there is nothing else exceptional about the man apart from being a thoroughly unlikeable and harmful person, in my view.
- ThrowawayR2 4y ago
  "In 1979, Bill Gates and Christos Papadimitriou gave a lower bound of 1.06n flips and an upper bound of (5n+5)/3. The upper bound was improved, thirty years later, to 18n/11 by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough." --https://en.wikipedia.org/wiki/Pancake_sorting https://en.wikipedia.org/wiki/Pancake_sorting The original paper seems to be https://www.sciencedirect.com/science/article/pii/0012365X79900682?via%3Dihub https://www.sciencedirect.com/science/article/pii/0012365X79... Rather interesting, I didn't know that about his history either.
  - oska 4y ago
    > The original paper seems to be https://www.sciencedirect.com/science/article/pii/0012365X79 https://www.sciencedirect.com/science/article/pii/0012365X79... Cheers. I've found the full paper is accessible through Sci-Hub [1]. I've had a very quick glance over it. The paper was submitted in January 1978 (when he'd already been at Microsoft for 2 years). But this NPR transcript [2] of a chat with Gates' Harvard professor Harry Lewis describes him as coming up with the solution a few days after the professor referenced the problem in class (in either 1974 or '75). Gates' co-author Christos Papadimitriou was an assistant professor at Harvard at the time. Papadimitriou went on to a glittering academic career and he recounts his recollection of the collaboration with Gates in a 2013 ACM profile [3]. So it appears that I do have to concede Gates this one contribution towards computer science. Although the paper contains a somewhat intriguing note right at the bottom : > Ervin Györi of the Hungarian Academy of Sciences and György Turán of J. Atilla University have independently discovered a proof of Theorem 1 [the five-thirds solution]. Their algorithm and proof are essentially the same as ours. And their paper [4] was published in 1978, preceding publication of the Gates & Papadimitriou paper in 1979. [1] https://sci-hub.se/https://doi.org/10.1016/0012-365X(79)90068-2 https://sci-hub.se/https://doi.org/10.1016/0012-365X(79)9006... [2] https://web.archive.org/web/20110919161456/http://www.npr.org/templates/story/story.php?storyId=92236781 https://web.archive.org/web/20110919161456/http://www.npr.or... [3] https://www.acm.org/articles/people-of-acm/2013/christos-papadimitriou https://www.acm.org/articles/people-of-acm/2013/christos-pap... [4] https://scholar.google.com/citations?view_op=view_citation&hl=en&user=LbDqMpIAAAAJ&cstart=100&pagesize=100&sortby=pubdate&citation_for_view=LbDqMpIAAAAJ:i6LplTXqhpIC https://scholar.google.com/citations?view_op=view_citation&h...

by Verdex 4y ago

oska 4y ago

I strongly doubt that Gates made any significant contributions to computer science. So I'd appreciate a source to what you've claimed here. Gates had a 'genius' for ruthlessly exploiting a monopoly in business; apart from that there is nothing else exceptional about the man apart from being a thoroughly unlikeable and harmful person, in my view.

ThrowawayR2 4y ago
"In 1979, Bill Gates and Christos Papadimitriou gave a lower bound of 1.06n flips and an upper bound of (5n+5)/3. The upper bound was improved, thirty years later, to 18n/11 by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough." --https://en.wikipedia.org/wiki/Pancake_sorting https://en.wikipedia.org/wiki/Pancake_sorting The original paper seems to be https://www.sciencedirect.com/science/article/pii/0012365X79900682?via%3Dihub https://www.sciencedirect.com/science/article/pii/0012365X79... Rather interesting, I didn't know that about his history either.
- oska 4y ago
  > The original paper seems to be https://www.sciencedirect.com/science/article/pii/0012365X79 https://www.sciencedirect.com/science/article/pii/0012365X79... Cheers. I've found the full paper is accessible through Sci-Hub [1]. I've had a very quick glance over it. The paper was submitted in January 1978 (when he'd already been at Microsoft for 2 years). But this NPR transcript [2] of a chat with Gates' Harvard professor Harry Lewis describes him as coming up with the solution a few days after the professor referenced the problem in class (in either 1974 or '75). Gates' co-author Christos Papadimitriou was an assistant professor at Harvard at the time. Papadimitriou went on to a glittering academic career and he recounts his recollection of the collaboration with Gates in a 2013 ACM profile [3]. So it appears that I do have to concede Gates this one contribution towards computer science. Although the paper contains a somewhat intriguing note right at the bottom : > Ervin Györi of the Hungarian Academy of Sciences and György Turán of J. Atilla University have independently discovered a proof of Theorem 1 [the five-thirds solution]. Their algorithm and proof are essentially the same as ours. And their paper [4] was published in 1978, preceding publication of the Gates & Papadimitriou paper in 1979. [1] https://sci-hub.se/https://doi.org/10.1016/0012-365X(79)90068-2 https://sci-hub.se/https://doi.org/10.1016/0012-365X(79)9006... [2] https://web.archive.org/web/20110919161456/http://www.npr.org/templates/story/story.php?storyId=92236781 https://web.archive.org/web/20110919161456/http://www.npr.or... [3] https://www.acm.org/articles/people-of-acm/2013/christos-papadimitriou https://www.acm.org/articles/people-of-acm/2013/christos-pap... [4] https://scholar.google.com/citations?view_op=view_citation&hl=en&user=LbDqMpIAAAAJ&cstart=100&pagesize=100&sortby=pubdate&citation_for_view=LbDqMpIAAAAJ:i6LplTXqhpIC https://scholar.google.com/citations?view_op=view_citation&h...