Top 150 computer science events to be decided once and for all
Today I break Shtetl-Optimized‘s long radio silence with a relatively-exciting announcement: you remember my timeline of computer science history? Well, MIT students Jason Zhu and Ammar Ammar have now kindly created a website where you can vote on each of the entries, as well as new entries suggested by commenters. It’s pretty simple: you just register (by entering an email address, username, and password), then upvote each entry you like and downvote each entry you dislike (you can also abstain on any entry).
The voting site arrives just in time for the MIT symposium “Computation and the Transformation of Practically Everything”, which is happening today and tomorrow.
For reference, here are the 17 new contenders added by popular demand:
150BC Chinese text describes Gaussian elimination
499 Indian mathematician Aryabhata describes the “kuttaka” algorithm for solving Diophantine equations
1206 al-Jazari builds elaborate water clocks and musical automata
1801 The Jacquard loom uses punched cards to control textile manufacturing
1951 Wilkes, Wheeler, and Gill describe the concept of closed subroutines
1956 Stephen Kleene invents regular expressions
1962 The Atlas computer begins operation in Manchester
1962 Robert Gallager introduces low-density parity check codes
1968 First deployed packet-switching network
1969 Strassen’s algorithm for fast matrix multiplication
1969 Stephen Wiesner conceives of quantum money and multiplexing
1971 Vapnik and Chervonenkis introduce VC dimension
1982 PostScript
1992 The PCP Theorem
1999 SETI@home
2006 DaVinci surgical robot performs the first unaided operation
2007 Checkers solved
Update: A new feature has been added that lets you rank four randomly-selected entries—click “Done” on the bottom of the page to access it.
Update: You can now undo a vote by clicking twice on the same arrow.
Follow
Comment #1 April 11th, 2011 at 12:12 pm
As a computer scientist I’m offended the interface for the sorting of importance of events doesn’t depend on the swapping of two elements! Really, there are at least 150 elements in the list. You ought to have exposed the root level of Mergesort, asking each person to make only simple comparisons. As it stands you’re asking me to implement Bubblesort. My time is more precious.
Also, there appears to be a bug? “Euclid’s Elements” shows up in my list to sort by importance at least three times. There are several others behaving the same way. (Maybe clicking on the “accept checkmark” multiple times adds a topic to the sort by importance list multiple times?)
Otherwise, I think its great you’ve created this collaborative tool.
Comment #2 April 11th, 2011 at 12:50 pm
Ross: Not only did we consider a comparison-based voting system, but Ammar and his adviser have a prototype of such a system that we’re planning to test a bit later (as an alternative to the current up-or-down system). However, comparison-based voting has drawbacks of its own for this application: I don’t WANT to have to decide whether MS Office was more or less important than the Time Hierarchy Theorem. Instead, I just want to express my approval or disapproval for the subset of entries I care about.
Comment #3 April 11th, 2011 at 12:50 pm
As for the bug: sorry, we’ll look into it!
Comment #4 April 11th, 2011 at 12:53 pm
Just voted!
Comment #5 April 11th, 2011 at 1:42 pm
OK, Ammar tells me the bug is fixed now.
Comment #6 April 11th, 2011 at 1:45 pm
some additional features i wouldn’t mind seeing: mark an entry as having a bug (error, incomplete, etc); mark entries as duplicates/closely enough related to be considered for merging (i can envisage having a main entry that will be published that is most representative of a given achievement and additional entries that are closely related which perhaps would show up as footnotes or only in the electronic version of the list).
Comment #7 April 11th, 2011 at 5:07 pm
A problem: There’s no way to undo a vote, except by changing it to the other! I can change from down to up but not from down to neutral.
Comment #8 April 11th, 2011 at 5:17 pm
Sniffnoy: Thanks for pointing that out! I’ve asked Jason and Ammar to fix it.
Comment #9 April 11th, 2011 at 9:38 pm
Hey Scott, love the site. One issue: once you vote something up or down there’s no way to change your vote back to neutral. Maybe you could click on your up vote and have it reset?
Comment #10 April 12th, 2011 at 3:18 am
Hmmm…..
It’s “Wiener”, not “Weiner”.
The site definitely shows that being knowledgeable in Computer Science does not a good website developer make.
Comment #11 April 12th, 2011 at 9:02 am
For starters, the word “bug” wasn’t coined in 1947. The moth trapped in a relay was noted because the word bug has been used in engineering since at least the 19th century, and may even go back to the middle ages.
No Boyer-Moorse string search algorithm?
You list the Pentium FDIV bug, but not on followup work by Intel and AMD in using formal methods to verify their processors.
You don’t important dates for the introduction of important software for formal method, such as ACL2, Coq, Isabelle, Agda, NuPrl (1979), LEGO, etc. Not even mention of the first rudimentary theorem provers.
You don’t list Martin-Löf’s work on constructive set theory, which is (by some) considered the most important book in logic written in the past 50 years, and is the foundation for emerging dependently-typed programming languages (Agda, Epigram, etc.)
Haskell is important for being the first “pure” functional language. Monads are not mentioned at all, which are very important. Likewise, no mention of category theory, also very important for theoretical computer science.
Nothing about the invention of Prolog or the WAM compiler.
No mention of Gentzen and the invention of natural deduction/sequent calculi, which are so important for logic programming and type inference?
No mention of intuitionistic logic at all? (Brouwer, or Heyting’s formalisation, or Komolgorov semantics)?!!!
No mention of Girard and Linear Logic, etc.? Not only for substructural logics, but for resource analysis of computer programs much later.
No mention of the first fuzzy logics (Łukasiewicz in early 20th century, and later Zadeh in 60s)?
The invention of relational semantics for logics? (Beth, Hintikka, and Kripke) in the 1950s and 60s?
No mention of Leibniz’s work in calculus, which some consider more important than Newton.
No mention of Plotkin’s work connecting operational and denotational semantics?
No mention of Java programming language. (Controversial, but some might consider it to be an important milestone.) What about Pascal programming language?
Markov chains?
Beysian Inference?
No mention of Church’s introduction of the Lambda calculus?!?
There are so many, too many, *important* events in the history of computer science that are left out of this list.
Comment #12 April 12th, 2011 at 9:30 am
It’s a shame that MIT charges for the two-day event of talks. I wanted to hear Scott and Erik (Demaine) speak at the event, but unfortunately, it’s $25. I simply can’t afford it! Sorry MIT, but you’re already too rich for this. Shame.
Comment #13 April 12th, 2011 at 12:41 pm
WantedToHearScottAndErikButCantAffordIt: As someone pointed out to me, you can watch all the talks on streaming video, for free, starting tomorrow. (On the other hand, without coughing up $25 you can’t enjoy the delicious boxed lunches.)
Comment #14 April 12th, 2011 at 4:53 pm
There’s nothing like doing a lot of hard work and releasing a tool to the world only to receive negative feedback.
I didn’t mean to be harsh on your student developers. I think the site is a great idea. I’m voting now.
Comment #15 April 13th, 2011 at 6:21 am
“There’s nothing like doing a lot of hard work and releasing a tool to the world only to receive negative feedback.”
You took the redpill. Welcome to the Terror of the Real.
Comment #16 April 14th, 2011 at 10:51 am
There’s one thing I would have certainly put forward but it’s not on your list. I can understand why it’s not, but that’s a pity. Maybe you should include a mechanism so that outsiders can add some events they think should be voted for, such as the appearance of this paper:
http://arxiv.org/abs/1011.3245
😉
Comment #17 April 14th, 2011 at 4:39 pm
Scott,
How about Len Adleman’s demonstration in 1994 of how DNA can be used for computation? Sure it was only for DNA but the idea of using molecules or biological entities such as bacteria or viruses for computation seems to be worthy of mention (even if it’s not specifically Adleman’s demonstration).
Comment #18 April 14th, 2011 at 5:56 pm
Vladimir: I didn’t feel DNA computing had led to enough either practically or theoretically. But maybe (e.g.) something about biological self-assembly should’ve been there…
Comment #19 April 15th, 2011 at 12:59 am
Allow me a brief interruption. For the many SO participants who enjoy a good chuckle when another of Noam Chomsky’s dingbat theories gets trashed, check out:
http://www.sciencedaily.com/releases/2011/04/110414065107.htm
Comment #20 April 15th, 2011 at 8:33 pm
Scott, it’s a bit late, but re “Building on earlier breakthroughs by Polish mathematician Marian Rejewski, …” I wish you could add (at minimum) “and colleagues”, referring to Henryk Zygalski and Jerzy Różycki. There are biographies of them in Wikipedia, and nobody remembers the other two guys. Jerzy Różycki died in 1942 on board a ship that sunk under unclear circumstances, while Rejewski and Zygalski went on to live long lives.
Comment #21 April 15th, 2011 at 8:37 pm
I keep clicking the blue links above the timeline entries, expecting to reach informative pages about the topics, oh well. Maybe some could be linked to wikipedia?
Comment #22 April 16th, 2011 at 6:06 am
>> DaVinci surgical robot performs the first unaided operation
the wording of this entry is quite misleading, since at all times the surgeon is in full control of the robot.
Comment #23 April 16th, 2011 at 2:42 pm
You said you can watch the Symposium videos online? Anyone have a link? Can’t find it.
Comment #24 April 17th, 2011 at 8:29 pm
Norbert Wiener’s famous work on cybernetics is a book, not a paper.
Norbert Wiener (1948), Cybernetics or Control and Communication in the Animal and the Machine, (Hermann & Cie Editeurs, Paris, The Technology Press, Cambridge, Mass., John Wiley & Sons Inc., New York, 1948).
Comment #25 April 18th, 2011 at 3:28 pm
@22 I found this “Some argue, however, that perhaps the greatest leap took place in Rome in 2006, when a team of
physicians in Boston, MA, monitored a robotic surgical
system performing an undisclosed heart procedure
unaided. The procedure took approximately 50
minutes and was performed solely by the robot.”
Ref: http://www.premierinc.com/about/news/inthenews/fundamentals-of-robotic-surgical-systems.pdf
Barrett Franklin
“Robotic Surgical Systems”
Biomedical Instrumentation & Technology, Nov./Dec. 2006, p.461
Comment #26 April 23rd, 2011 at 2:59 am
What about cisc vs risc, or even vliw and epic. What about developments concerning the memory wall and other design developments (like cache hierachies) to minimize practical bottlenecks in computing.
Comment #27 May 18th, 2011 at 2:20 am
What about Jack Edmond’s 1965 paper, “Paths, Trees, and Flowers”, which made the distinction between “finite” and “algebraic” programs, and led the way to the P, NP, and co-NP categorization?