I see some of my favourites among other replies. I don't think I see these:
Ask HN: What is your favorite CS paper?
191–200 of 265 posts
Re: Ask HN: What is your favorite CS paper?
#192I would say An Agent-Oriented Programming by Yoav Shoham. It certainly set my mind going and made me think about how programs could be organized. I still think, agents, systems of agents, and mobile agent code has a place in computing. Even though some form of RPC over HTTP won over mobile code, I look at the spinning up of VMs and cannot help but think that agents have a place. Combined with the tuple space stuff from Yale, I still see a powerful way to go forward.
1) 1990 http://cife.stanford.edu/node/599
2) 1993 http://faculty.cs.tamu.edu/ioerger/cs631-fall05/AOP.pdf
Re: Ask HN: What is your favorite CS paper?
#193Delegation is Inheritance
Re: Ask HN: What is your favorite CS paper?
#194Relevance Vector Machines by Tipping
or
Homomorphic Encryption over the Integers
Re: Ask HN: What is your favorite CS paper?
#195Earlier quoted context omitted.
Discrimination runs in linear time not in the number of items but in the total size of the data. If you have n items each of size k it takes O(kn). Conventional sorting often assumes that you can compare keys of size k in constant time and therefore gets O(n lg n) but a more honest analysis would yield O(kn log n) for (say) merge sort.
The bound on string sorting is typically written as O(n log n + D), where D is the sum of distinguishing prefixes, ie input length minus some fluff. Since D >= n log n we already have linearity on input length.
Are you saying that you can sort strings in O(n log n + D) using a conventional sorting algorithm such as merge sort? If so, I don't understand why D would be an additive factor implying that each string is only involved in a constant number of comparisons.
(I wasn't, by the way, only considering strings when discussing variable sized keys -- the beauty of discrimination is that we essentially reduce all sorting problems to string sorting.)
Re: Ask HN: What is your favorite CS paper?
#196"Reflections on Trusting Trust" by Ken Thompson is one of my favorites. Most papers by Jon Bentley (e.g. A Sample of Brilliance) are also great reads. I'm a frequent contributor to Fermat's Library, which posts an annotated paper (CS, Math and Physics mainly) every week. If you are looking for interesting papers to read, I would strongly recommend checking it out - http://fermatslibrary.com/ - Reflections on Trusting…
The Ken Thompson Hack is a haunting idea. The intelligence agencies almost certainly would've tried to implement it at some point.
You can actually detect the issue in Trusting Trust: https://www.schneier.com/blog/archives/2006/01/countering_tr...
If you have two compilers and one is open source (and you've read the source and happy that it's clean), you can compile that source with both compilers. The output will be different because the two compilers will make different optimizations. However, now you have two binaries of the same compiler and while they aren't the same, their output will be. So you can re-compile the source with both new binaries and you should get a bit-for-bit equivalent output.
Re: Ask HN: What is your favorite CS paper?
#197"A Mathematical Theory of Communication" - Claude E. Shannon http://math.harvard.edu/~ctm/home/text/others/shannon/entrop...
Definition of a fairly important term from that paper...
"If the base 2 is used the resulting units may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey"
Re: Ask HN: What is your favorite CS paper?
#198I've been trying to get it frontpaged because, despite it's length, it's perhaps one of the most startling papers of this decade. Sadly, it seems like the HN voting gestalt hasn't decided to upvote a paper that's the CS equivalent of breaking the speed of light: "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" -> http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... (if you're d…
This is a nice technique in theory, but in practice it isn't so fast, mainly because of the implementation details. Radix sort is actually faster than comparison sorts if implemented well.
Re: Ask HN: What is your favorite CS paper?
#199Anything dealing w/ "reversible computing", makes you ask "what-if" ...
http://cqi.inf.usi.ch/qic/80_Toffoli.pdf
https://www.eng.famu.fsu.edu/~mpf/Frank-99-PhD-bookmarked.pd...
Re: Ask HN: What is your favorite CS paper?
#200"Reflections on Trusting Trust" by Ken Thompson is one of my favorites. Most papers by Jon Bentley (e.g. A Sample of Brilliance) are also great reads. I'm a frequent contributor to Fermat's Library, which posts an annotated paper (CS, Math and Physics mainly) every week. If you are looking for interesting papers to read, I would strongly recommend checking it out - http://fermatslibrary.com/ - Reflections on Trusting…
This is a really nice site, but the owner should really enable HTTPS if they want people to give their email address over for the newsletter
second!