22 ms·

Ask HN: What is your favorite CS paper?

• tjr 9y ago
  Growing a Language
  • andars 9y ago
    Guy L. Steele. https://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf https://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf
• 0xf8 9y ago
  "A Mathematical Theory of Communication" - Claude E. Shannon http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf http://math.harvard.edu/~ctm/home/text/others/shannon/entrop...
  • godelmachine 9y ago
    All time hit paper
    • rhaps0dy 9y ago
      I like the papers that describe the OOPS and the Gödel Machine :)
  • ape4 9y ago
    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"
• Phithagoras 9y ago
  Not exactly CS, but the Unreasonable Effectiveness of Mathematics in the Natural Sciences is one of my favourites.
• gregors 9y ago
  "Reflections on Trusting Trust" - Ken Thompson https://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf https://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thomp...
  • dkaoster 9y ago
    Seconded.
  • noobtube 9y ago
    this is the bomb.
• alok-g 9y ago
  Automated Theorem Proving, David Plaisted http://onlinelibrary.wiley.com/doi/10.1002/wcs.1269/full http://onlinelibrary.wiley.com/doi/10.1002/wcs.1269/full
• Jtsummers 9y ago
  Not a paper, and not strictly CS, but Mythical Man-Month by Brooks. It solidified the connection in my mind between systems engineering and software engineering. Other readings since then have extended and changed this understanding, but this is where my approach to software development started to mature.
  • monocasa 9y ago
    And I'd add the paper that inspired Brooks, Melvin Conway's "How Do Committees Invent?". http://www.melconway.com/Home/Committees_Paper.html http://www.melconway.com/Home/Committees_Paper.html
• 1001101 9y ago
  New Directions in Cryptography - Diffie + Hellman https://www-ee.stanford.edu/~hellman/publications/24.pdf https://www-ee.stanford.edu/~hellman/publications/24.pdf
• donquichotte 9y ago
  Not CS, but control theory: "Guaranteed Margins for LQG Regulators" by John C. Doyle. The abstract is just three words: "There are none." http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.362.8807&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.362...
• lukego 9y ago
  Back To The Future (Squeak). http://ftp.squeak.org/docs/OOPSLA.Squeak.html http://ftp.squeak.org/docs/OOPSLA.Squeak.html
• xixixao 9y ago
  Notation as a Tool of Thought, Kenneth E. Iverson http://www.jsoftware.com/papers/tot.htm http://www.jsoftware.com/papers/tot.htm
  • evanb 9y ago
    Also along those lines: Two notes on notation, Knuth, https://arxiv.org/abs/math/9205211 https://arxiv.org/abs/math/9205211
• thristian 9y ago
  Out Of The Tarpit, by Moseley and Marks https://github.com/papers-we-love/papers-we-love/blob/master/design/out-of-the-tar-pit.pdf https://github.com/papers-we-love/papers-we-love/blob/master... The first half of the paper is a spot-on critique of so many things that go wrong in the process of designing and implementing large-scale software systems. The second half, where the authors propose a solution, kind of goes off the rails a bit into impracticality... but they definitely point in a promising direction, even if nobody ever uses their concrete suggestions.
  • nuclx 9y ago
    Definitely a gem. I loved their accurate comparison of the common programming paradigms, though I have to admit, that I didn't follow their idea of functional relational programming in detail.
  • agentm 9y ago
    Project:M36 is an implementation of the proposed design from the "Out of the Tarpit" paper. https://github.com/agentm/project-m36 https://github.com/agentm/project-m36
• chadash 9y ago
  It might be a cliche one to pick, but I really really really enjoy Alan Turing's "Computing Machinery and Intelligence"[1]. This paper straddles the line between CS and philosophy, but I think it's an important read for anyone in either field. And a bonus is that it's very well-written and readable. [1] https://www.csee.umbc.edu/courses/471/papers/turing.pdf https://www.csee.umbc.edu/courses/471/papers/turing.pdf
  • AndrewOMartin 9y ago
    Thanks for picking that one, that means I don't have to choose between it and my joint favourite, the snappily titled "Why Heideggerian AI Failed and how Fixing it would Require making it more Heideggerian". Where Turing's paper put us on the journey towards AI, 57 years later Dreyfus points out how the direction chosen is not only wrong, but hopelessly misguided. [quote] As I studied the RAND papers and memos, I found to my surprise that, far from replacing philosophy, the pioneers in CS and AI had learned a lot, directly and indirectly from the philosophers. They had taken over Hobbes’ claim that reasoning was calculating, Descartes' mental representations, Leibniz's idea of a "universal characteristic" - a set of primitives in which all knowledge could be expressed, -- Kant’s claim that concepts were rules, Frege's formalization of such rules, and Wittgenstein's postulation of logical atoms in his Tractatus. In short, without realizing it, AI researchers were hard at work turning rationalist philosophy into a research program. [endquote] http://leidlmair.at/doc/WhyHeideggerianAIFailed.pdf http://leidlmair.at/doc/WhyHeideggerianAIFailed.pdf
  • icc97 9y ago
    Given the far reaching importance of the Turing test, it's amazing how readable and understandable the paper is.
    • Retra 9y ago
      I really don't see how anyone would take that as a given.
• throwaway1e100 9y ago
  Real programmers don't use Pascal The rise of worse is better
• nikhizzle 9y ago
  Without a doubt. Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport. http://amturing.acm.org/p558-lamport.pdf http://amturing.acm.org/p558-lamport.pdf My first introduction to time scales as a partial ordering. Very mind opening.
  • e12e 9y ago
    A somewhat lighter take on similar issues that I also enjoyed was: "Designing croquet's TeaTime: a real-time, temporal environment for active object cooperation", David Reed : http://dl.acm.org/citation.cfm?id=1094855.1094861 http://dl.acm.org/citation.cfm?id=1094855.1094861
  • navneet4735 9y ago
    Exactly I worked my way backwards to this paper while exploring real world distributed systems like Kafka and Zookeeper and it was exceptionally well written paper that explained the basics of building distributed systems
  • deleted 9y ago
    [deleted]
  • lukateake 9y ago
    Your link is throwing a 404 for me. I found it here: https://www.ics.uci.edu/~cs230/reading/time.pdf https://www.ics.uci.edu/~cs230/reading/time.pdf
    • nikhizzle 9y ago
      That is not the paper. It appears to be a summary.
  • mikhailfranco 9y ago
    Never did it for me. Always seemed totally trivial. What else could it possibly be!? It seems like a direct simplification of Einstein (... no global time ... spatially separated locations communicate with signals ... signals propagate in finite time ... proper time is an ordering along a world line ... relative time depends on communication ... there are spacelike separations where events do not have a defined temporal order ...). I guess they had first access to the fruit tree in those days. I once spoke to Henri Gouraud after he gave a talk. He was very self-deprecating and acutely embarrassed that his name was attached to a blindingly obvious first-thing-that-comes-into-your-head shading expression-that-barely-deserves-the-name-algorithm. Sometimes that low hanging stuff gives you stomach ache.
• emidln 9y ago
  A bit cliche for HN, but I really enjoyed RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) by John McCarthy[0]. It was accessible to someone whose background at the time was not CS and convinced me of the beauty of CS -- and lisp. [0] - http://www-formal.stanford.edu/jmc/recursive.html http://www-formal.stanford.edu/jmc/recursive.html
• jasode 9y ago
  "The Limits of Correctness" (1985) by Bryan Cantwell Smith: https://www.student.cs.uwaterloo.ca/~cs492/11public_html/p18-smith.pdf https://www.student.cs.uwaterloo.ca/~cs492/11public_html/p18... I know Thompson's "Reflections on Trust" and Shannon's "Communication" papers are more famous but I believe BCS's "Correctness" paper has more immediate relevance to a wider population of programmers. For example, I don't believe Ethereum's creator, Vitalik Buterin, is familiar with it because if he was, he would have realized that "code is law" is not possible and therefore he would have predicted the DAO hack and subsequent fork/reversal to undo the code. Seriously, if you read BCS's paper and generalize its lessons learned, you will see that the DAO hack and its reversal as inevitable.
  • catnaroek 9y ago
    > you will see that the DAO hack and its reversal as inevitable. Honest naïve question. What's the proof?
    • throwawayjava 9y ago
      FWIW I think this is a very fair question. Parent's post veers a bit further toward defeatism than I think Smith's paper advocates for or justifies. In particular, of course the DAO hack wasn't inevitable -- a more careful programmer could've foreseen and prevented that attack and whole other classes of attack.
      • tom_mellior 9y ago
        Part of the linked paper's point is that because computer systems involve many "levels of failure", even a more careful programmer cannot usually rule out every class of programs. The DAO hack, yes, possibly. But, for example, people have also lost money due to bugs in the Solidity compiler: https://np.reddit.com/r/ethtrader/comments/5foa5p/daily_discussion_30nov2016/dalxys1/ https://np.reddit.com/r/ethtrader/comments/5foa5p/daily_disc... How many "more careful" Ethereum programmers also check the compiler for correctness? Another paper in this vein is James Fetzer's "Program Verification: The Very Idea". http://lore.ua.ac.be/Teaching/SSPEC2LIC/critique2.pdf http://lore.ua.ac.be/Teaching/SSPEC2LIC/critique2.pdf
• pradn 9y ago
  My favorite paper in computer systems is "Memory Resource Management in VMware ESX Server". It identifies a problem and devises several clever solutions to the problem. I love papers that make your go "AHA!". http://web.eecs.umich.edu/~mosharaf/Readings/ESX-Memory.pdf http://web.eecs.umich.edu/~mosharaf/Readings/ESX-Memory.pdf
• microbie 9y ago
  Dijkstra's shortest path algorithm in "A Note on Two Problems in Connexion with Graphs" http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.... Pure, mathematical and a great impact on both how to prove and define algorithms as well as the problem itself.
• brad0 9y ago
  Kademlia, a P2P distributed hash table. DHTs are very complex from the outside but very simple once you understand the building blocks. https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia...
  • zzzcpan 9y ago
    Hmm, I think it's important to understand Chord DHT first and only after that move on to Kademlia, then S/Kademlia and so on.
• efferifick 9y ago
  Producing Wrong Data without Doing Anything Obviously Wrong. Immediately useful for anyone measuring compiler transformations performance!
  • tom_mellior 9y ago
    Great paper, yes. Immediately useful? More like disheartening, because it doesn't really tell you how to be sure your measurements are OK.
    • jvilk 9y ago
      Our lab addressed some of the issues with Stabilizer [0], which "eliminates measurement bias by comprehensively and repeatedly randomizing the placement of functions, stack frames, and heap objects in memory". [0] http://plasma.cs.umass.edu/emery/stabilizer.html http://plasma.cs.umass.edu/emery/stabilizer.html "Stabilizer: Statistically Sound Performance Evaluation" by Charlie Curtsinger and Emery Berger, ASPLOS 2013
  • michaelmior 9y ago
    Link: https://www.eecs.northwestern.edu/~robby/courses/322-2013-spring/mytkowicz-wrong-data.pdf https://www.eecs.northwestern.edu/~robby/courses/322-2013-sp...
• wsxiaoys 9y ago
  Cheney on the MTA http://home.pipeline.com/~hbaker1/CheneyMTA.html http://home.pipeline.com/~hbaker1/CheneyMTA.html Full tail recursion scheme implementation by never "return" in C
  • twoodfin 9y ago
    Such a great hack. Not only tail recursion but a complete GC implementation in (almost) platform-independent generated C code.
• megamindbrian 9y ago
  My favorite topic was from an advanced user interfaces class. Describe 3 example of a bad user experience where the input in to the system does not give you the expected output. My poor example was a Kleenex box, I try to pull on one Kleenex and it tears or two come out at a time.
• exelius 9y ago
  The Mythical Man-Month https://www.cs.drexel.edu/~yfcai/CS451/RequiredReadings/MythicalManMonth.pdf https://www.cs.drexel.edu/~yfcai/CS451/RequiredReadings/Myth...
  • monocasa 9y ago
    And the paper that inspired it, Melvin Conway's "How Do Committees Invent?" http://www.melconway.com/Home/Committees_Paper.html http://www.melconway.com/Home/Committees_Paper.html
    • exelius 9y ago
      This is great -- I never knew about this paper but it reinforces a lot of things I learned. Namely, if you want to know how a company really works, ignore the org charts and map the systems architecture (a corollary to the author's thesis). That it still holds true almost 50 years later is pretty amazing.
  • kabdib 9y ago
    Favorite quote: "I gave my manager two copies of this book so he could read it twice as fast."
• 0xf8 9y ago
  The Applications of Probability to Cryptography - Alan M. Turing https://arxiv.org/abs/1505.04714 https://arxiv.org/abs/1505.04714
• akkartik 9y ago
  Hofstadter, D. R. and Mitchell, M. (1995). "The Copycat project: A model of mental fluidity and analogy-making." Chapter 5 in D. R. Hofstadter, Fluid Concepts and Creative Analogies. http://web.cecs.pdx.edu/~mm/CopycatChapter.html http://web.cecs.pdx.edu/~mm/CopycatChapter.html "Copycat is a model of analogy making and human cognition based on the concept of the parallel terraced scan, developed in 1988 by Douglas Hofstadter, Melanie Mitchell, and others at the Center for Research on Concepts and Cognition, Indiana University Bloomington. Copycat produces answers to such problems as "abc is to abd as ijk is to what?" (abc:abd :: ijk:?). Hofstadter and Mitchell consider analogy making as the core of high-level cognition, or high-level perception, as Hofstadter calls it, basic to recognition and categorization. High-level perception emerges from the spreading activity of many independent processes, called codelets, running in parallel, competing or cooperating. They create and destroy temporary perceptual constructs, probabilistically trying out variations to eventually produce an answer. The codelets rely on an associative network, slipnet, built on pre-programmed concepts and their associations (a long-term memory). The changing activation levels of the concepts make a conceptual overlap with neighboring concepts." -- https://en.wikipedia.org/wiki/Copycat_(software) https://en.wikipedia.org/wiki/Copycat_(software) https://cogsci.indiana.edu/copycat.html https://cogsci.indiana.edu/copycat.html
• gnaritas 9y ago
  Not a paper, but one of my favorite talks https://www.youtube.com/watch?v=_ahvzDzKdB0&t=642s https://www.youtube.com/watch?v=_ahvzDzKdB0&t=642s Growing a Language by Guy Steele (co-inventory of Scheme). Brilliant speech about how to grow languages and why it's necessary. Languages that can be grown by the programmer, like Lisp or Smalltalk are better than languages that fixed like most others, this is why.
  • deleted 9y ago
    [deleted]
• twoodfin 9y ago
  Cheating a little, but the collected Self papers are what I'd bring to a desert island: https://www.cs.ucsb.edu/~urs/oocsb/self/papers/papers.html https://www.cs.ucsb.edu/~urs/oocsb/self/papers/papers.html
  • zachsnow 9y ago
    "Self: the power of simplicity" really lives up to its name!
• agentultra 9y ago
  Most of my favourites have already been listed but one I found particularly interesting was Von Neumann's Theory of Self-Reproducing Automata [0]. [0] http://cba.mit.edu/events/03.11.ASE/docs/VonNeumann.pdf http://cba.mit.edu/events/03.11.ASE/docs/VonNeumann.pdf
  • yaseer 9y ago
    +1 to this. Von Neumann was well ahead of his time with his automata ideas. I found in interesting how both Von Neumann and Turing turned to analyse biological systems later in their careers.
    • ehudla 9y ago
      Some of you might be interested in an essay I wrote about von Neumann and Norbert Wiener that gives some of the background and context of this work. http://www.ehudlamm.com/outsiders.pdf http://www.ehudlamm.com/outsiders.pdf
• nonsince 9y ago
  Type Systems as Macros http://www.ccs.neu.edu/home/stchang/popl2017/ http://www.ccs.neu.edu/home/stchang/popl2017/ It's not world-changing or even particularly novel, but it's such a simple concept explained very well that really changes how you see the typed/dynamic language divide, as well as language design in general.
• flavio81 9y ago
  Automated Distributed Execution of LLVM code using SQL JIT Compilation As collected by the SIGBOVIK group: http://sigbovik.org/2017/proceedings.pdf http://sigbovik.org/2017/proceedings.pdf Quote: "Following the popularity of MapReduce, a whole ecosystem of Apache Incubator Projects has emerged that all solve the same problem. Famous examples include Apache Hadoop, Apache Spark, Apache Pikachu, Apache Pig, German Spark and Apache Hive [1]. However, these have proven to be unusable because they require the user to write code in Java. Another solution to distributed programming has been proposed by Microsoft with their innovative Excel system. In large companies, distributed execution can be achieved using Microsoft Excel by having hundreds of people all sitting on their own machine working with Excel spreadsheets. These hundreds of people e combined can easily do the work of a single database server." PS: This thread is great, i'm bookmarking because here there are good (serious) papers.
  • jlisam13 9y ago
    Apache Pikachu got me
    • rhaps0dy 9y ago
      The alliteration is real
  • godelmachine 9y ago
    Me, too bookmarking!
• akkartik 9y ago
  Peter Naur, "Programming as theory building." (1985) “…programming properly should be regarded as an activity by which the programmers form or achieve a certain kind of insight, a theory, of the matters at hand. This suggestion is in contrast to what appears to be a more common notion, that programming should be regarded as a production of a program and certain other texts.” http://pages.cs.wisc.edu/~remzi/Naur.pdf http://pages.cs.wisc.edu/~remzi/Naur.pdf https://news.ycombinator.com/item?id=10833278 https://news.ycombinator.com/item?id=10833278 https://news.ycombinator.com/item?id=7491661 https://news.ycombinator.com/item?id=7491661
  • defined 9y ago
    This really is a paper with deep implications. One of them, as I understand it, is that in any significant software project, regardless of the volume and quality of the documentation, or quality of the code base, maintainers not involved in building the original project will not be able to build the "theory" correctly in their minds, and will consequently make changes that are clumsy or detrimental. (I'm summarizing, so some important aspects have been skipped). I see this aspect of the paper as related to the "conceptual integrity" discussed in the Mythical Man-Month. This paper has long been one of my favorites, and was first brought to my attention when I was reading (IIRC) one of Alistair Cockburn's books. Sadly, few of the people I shared it with found it interesting.
    • akkartik 9y ago
      It's at the core of my software life for several years now: http://akkartik.name/about http://akkartik.name/about
• kwisatzh 9y ago
  How to share a secret by Adi Shamir. Simple, elegant, short and highly impactful.
  • llimllib 9y ago
    http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf
• cozzyd 9y ago
  http://www.scs.stanford.edu/~dm/home/papers/remove.pdf http://www.scs.stanford.edu/~dm/home/papers/remove.pdf
  • lioeters 9y ago
    Love the figures and references.
• Vervious 9y ago
  Paxos made simple. It's a very beautiful paper.
• random_comment 9y ago
  Depixelizing Pixel Art http://johanneskopf.de/publications/pixelart/paper/pixel.pdf http://johanneskopf.de/publications/pixelart/paper/pixel.pdf I think this paper is very cute and also technically interesting.
• lawn 9y ago
  Bitcoin: A Peer-to-Peer Electronic Cash System https://www.bitcoin.com/bitcoin.pdf https://www.bitcoin.com/bitcoin.pdf
• abhishekgahlot 9y ago
  Communicating Sequential Processes Hoare http://www.cs.ucf.edu/courses/cop4020/sum2009/CSP-hoare.pdf http://www.cs.ucf.edu/courses/cop4020/sum2009/CSP-hoare.pdf Facebook’s Distributed Data Store for the Social Graph https://research.fb.com/publications/tao-facebooks-distributed-data-store-for-the-social-graph-2/ https://research.fb.com/publications/tao-facebooks-distribut...
• nayuki 9y ago
  "Bitcoin: A Peer-to-Peer Electronic Cash System" https://bitcoin.org/bitcoin.pdf https://bitcoin.org/bitcoin.pdf
• otakucode 9y ago
  Admittedly a good portion of my appreciation is due to the title alone, but the paper and contents itself are very good as well: 'The Geometry of Innocent Flesh on the Bone: Return-into-libc without function calls' by Hovav Shacham http://cseweb.ucsd.edu/~hovav/dist/geometry.pdf http://cseweb.ucsd.edu/~hovav/dist/geometry.pdf
• Hernanpm 9y ago
  I sill find this interesting, if you are familiar with Dijkstra Algorithm. Finding the k Shortest Paths by D. Eppstein https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
• nrjames 9y ago
  Mine is "Image Quilting for Texture Synthesis and Transfer" by Efros and Freeman. It's simple enough to implement as a personal project and has some nice visual output. Plus, Wang tiles are cool and it's fun to learn more about them. https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/papers/efros-siggraph01.pdf https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/p...
  • BugsJustFindMe 9y ago
    On the same subject, I prefer the concurrently published "Image Analogies" paper ( http://www.mrl.nyu.edu/projects/image-analogies/ http://www.mrl.nyu.edu/projects/image-analogies/ ) because their described technique, while slow, just makes so much sense.
• romaniv 9y ago
  I don't have a favorite research paper, but there is a long Ph.D. thesis I've recently read in its entirety and found a lot of interesting ideas: Programming with Agents: http://alumni.media.mit.edu/~mt/thesis/mt-thesis-Contents.html http://alumni.media.mit.edu/~mt/thesis/mt-thesis-Contents.ht... Here is a short paper with a clear description of an ingenious idea. Engineered Robustness by Controlled Hallucination: http://web.mit.edu/jakebeal/www/Publications/NIAI-2008.pdf http://web.mit.edu/jakebeal/www/Publications/NIAI-2008.pdf I like the simplicity of it. Most CS researches seem to be afraid of describing things that are simple, even if those things are non-obviosu and valuable.
• bootsz 9y ago
  End-To-End Arguments in System Design http://web.mit.edu/Saltzer/www/publications/endtoend/endtoend.pdf http://web.mit.edu/Saltzer/www/publications/endtoend/endtoen...
• bluedino 9y ago
  "A Method for the Construction of Minimum-Redundancy Codes" https://www.ic.tu-berlin.de/fileadmin/fg121/Source-Coding_WS12/selected-readings/10_04051119.pdf https://www.ic.tu-berlin.de/fileadmin/fg121/Source-Coding_WS... I'm not sure if it was the fact that I was just a kid when I read it, but it was just so obvious and simple but so complicated and amazing at the same time.
• jules 9y ago
  A play on regular expressions: https://sebfisch.github.io/haskell-regexp/regexp-play.pdf https://sebfisch.github.io/haskell-regexp/regexp-play.pdf This paper explains a beautiful algorithm for matching regular expressions with a Socratic dialogue.
• jhpriestley 9y ago
  The Scheme papers are great http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html "On the Translation of Languages from Left to Right", by Knuth, I found much clearer and more illuminating than any of the secondary literature on LR(k) parsing.
  • twoodfin 9y ago
    I recall finding "Lambda: The Ultimate GOTO" to be mind-bending.
• wwarner 9y ago
  Probabilistic Topic Models http://www.cs.columbia.edu/~blei/papers/Blei2012.pdf http://www.cs.columbia.edu/~blei/papers/Blei2012.pdf
• mdhughes 9y ago
  Worse is Better http://wiki.c2.com/?WorseIsBetter http://wiki.c2.com/?WorseIsBetter
• notaharvardmba 9y ago
  Andrew Tridgell's PhD Thesis: https://www.samba.org/~tridge/phd_thesis.pdf https://www.samba.org/~tridge/phd_thesis.pdf Which documents the invention of rsync, it's a good read.
  • gcp 9y ago
    His KnightCap papers are also cool, .e.g http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124.6321&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124... AlphaGo learning from self-play? Tridgell did it in 1998.
• zachsnow 9y ago
  Olin Shivers's work on various control flow analyses, in particular the paper "CFA2: a context-free approach to control-flow analysis", is a really cool static analysis via abstract interpretation. Matt Might had a bunch of papers in a similar vein.
  • jules 9y ago
    I wonder if it is possible to express this analysis as a datalog program.
• dvirsky 9y ago
  The Anatomy of a Large-Scale Hypertextual Web Search Engine, by Brin and Page. Not only for the historical value of changing the world, and for the fact that it's very interesting and readable; It has personal value to me: the first CS paper I've ever read and it inspired me and changed the course of my life, literally. Also, it has some very amusingly naive (in hindsight) stuff in it, like: "Google does not have any optimizations such as query caching, subindices on common terms, and other common optimizations. We intend to speed up Google considerably through distribution and hardware, software, and algorithmic improvements. Our target is to be able to handle several hundred queries per second" http://infolab.stanford.edu/~backrub/google.html http://infolab.stanford.edu/~backrub/google.html
  • pmiller2 9y ago
    I was hoping this one would show up. It's a startlingly simple paper, which both made the idea easy to implement (PageRank algorithm can be implemented in around 10 lines of Python, give or take), and easy to game (viz. the rise of link farms). Recommended for anyone with the prerequisite 1 semester of linear algebra or equivalent.
• ChuckMcM 9y ago
  I've always enjoyed Finseth's Thesis on text editing, "A cookbook for an EMACS", which he turned into a book: https://www.finseth.com/craft/ https://www.finseth.com/craft/ and is available in epub form for free.
• whataretensors 9y ago
  The original GAN paper was pretty big for me. https://arxiv.org/pdf/1406.2661.pdf https://arxiv.org/pdf/1406.2661.pdf
• cs702 9y ago
  I would never call it my "all-time favorite" (no paper qualifies for that title in my book), but Satoshi Nakamoto's paper, "Bitcoin: A Peer-to-Peer Electronic Cash System" deserves a mention here, because it proposed the first-known solution to the double-spending problem in a masterless peer-to-peer network, with Byzantine fault tolerance (i.e., in a manner resistant to fraudulent nodes attempting to game the rules), via a clever application of proof-of-work: https://bitcoin.org/bitcoin.pdf https://bitcoin.org/bitcoin.pdf Others in this thread have already mentioned papers or opinionated essays that quickly came to mind, including "Reflections on Trusting Trust" by Ken Thompson, "A Mathematical Theory of Communication" by Claude Shannon (incredibly well-written and easy-to-follow given the subject matter), and "Recursive Functions of Symbolic Expressions and Their Computation by Machine" by John McCarthy. I would also mention "On Computable Numbers, with an Application to the Entscheidungsproblem" by Alan Turing, "On Formally Undecidable Propositions of Principia Mathematica And Related Systems" by Kurt Gödel, and "The Complexity of Theorem Proving Procedures" by Stephen Cook, but in my view these papers are 'unnecessarily' challenging or time-consuming to read, to the point that I think it's better to read textbooks (or popular works like "Gödel, Escher, and Bach" by Douglas Hofstadter) covering the same topics instead of the original papers. Still, these papers are foundational. Finally, I think "The Mythical Man-Month" by Fred Brooks, and "Worse is Better" by Richard Gabriel merit inclusion here, given their influence. This is by no means an exhaustive list. Many -- many -- other worthy papers will surely come to mind over the course of the day that I won't have a chance to mention here. There are many other good recommendations elsewhere in this thread, including papers/essays I have not yet read :-)
  • oculusthrift 9y ago
    maybe i'm a little stringent but if if isn't peer reviewed and in a journal, i don't consider it a paper.
    • majewsky 9y ago
      I guess that, given its impact, it's more peer-reviewed than most published papers.
• joaobatalha 9y ago
  "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/ http://fermatslibrary.com/ - Reflections on Trusting Trust (Annotated Version) - http://fermatslibrary.com/s/reflections-on-trusting-trust http://fermatslibrary.com/s/reflections-on-trusting-trust - A Sample of Brilliance (Annotated Version) - http://fermatslibrary.com/s/a-sample-of-brilliance http://fermatslibrary.com/s/a-sample-of-brilliance
  • tequila_shot 9y ago
    http://fermatslibrary.com/ http://fermatslibrary.com/ isn't opening. Help?
    • joaobatalha 9y ago
      Not sure what happened, it was down, but it seems to be back up now. team@fermatslibrary.com is usually pretty responsive
  • djhworld 9y ago
    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
    • skypather 9y ago
      second!
    • manigandham 9y ago
      Why? Emails are not private information.
  • wrinkl3 9y ago
    The Ken Thompson Hack is a haunting idea. The intelligence agencies almost certainly would've tried to implement it at some point.
• larkeith 9y ago
  The Night Watch by James Mickens is always a good read: https://www.usenix.org/system/files/1311_05-08_mickens.pdf https://www.usenix.org/system/files/1311_05-08_mickens.pdf
  • xenophonf 9y ago
    That's a good one, but I think "This World of Ours", Mickens' treatise on the practical realities of operational security (specifically keying material handling), should take the top spot: https://www.usenix.org/system/files/1401_08-12_mickens.pdf https://www.usenix.org/system/files/1401_08-12_mickens.pdf
    • larkeith 9y ago
      Ooh, I'll have to read that next time I have a few minutes. Thabks for the link!
    • Analemma_ 9y ago
      The nice thing about this one is that it actually does have some important kernels of truth amid all the hilarity. Especially this bit about threat models: > Basically, you’re either dealing with Mossad or not-Mossad. If your adversary is not-Mossad, then you’ll probably be fine if you pick a good password and don’t respond to emails from ChEaPestPAiNPi11s@ virus-basket.biz.ru. If your adversary is the Mossad, YOU’RE GONNA DIE AND THERE’S NOTHING THAT YOU CAN DO ABOUT IT More security researchers need to learn about that.
  • godelmachine 9y ago
    I read The Slow Winter by James Mickens. Reading that brought a revolutionary change in my thinking. Have bookmarked his Harvard profile, just in case he publishes any more articles.
• AnimalMuppet 9y ago
  Why Pascal Is Not My Favorite Programming Language, by Brian Kernighan http://www.cs.virginia.edu/~cs655/readings/bwk-on-pascal.html http://www.cs.virginia.edu/~cs655/readings/bwk-on-pascal.htm... No Silver Bullet, by Fred Brooks http://worrydream.com/refs/Brooks-NoSilverBullet.pdf http://worrydream.com/refs/Brooks-NoSilverBullet.pdf The original STL documentation https://www.sgi.com/tech/stl/table_of_contents.html https://www.sgi.com/tech/stl/table_of_contents.html
• ColonelTrick 9y ago
  Since I just love the impracticality of it, Bernard Chazelle's linear time triangulation is my fave. https://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf https://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.p...
• beefman 9y ago
  Backus - A Functional Style and Its Algebra of Programs https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Literature/Backus.pdf https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...
• wlesieutre 9y ago
  "Interactive Indirect Illumination Using Voxel Cone Tracing" by Crassin et al. As an architectural lighting guy, seeing realtime global illumination look this good in a game engine was fantastic. Parts of the algorithm I can understand, parts go over my head still, but the results are amazing. A big part of what I do at work is radiosity simulations in AGI32 which is of course more accurate (because it's trying to accurately simulate real world lighting results) but much much slower. http://research.nvidia.com/publication/interactive-indirect-illumination-using-voxel-cone-tracing http://research.nvidia.com/publication/interactive-indirect-...
  • web007 9y ago
    That link doesn't work for me, even though the same link is presented in a Google search. Also, for some reason I can't find it via search by DOI. http://research.nvidia.com/publication/interactive-indirect-illumination-using-voxel-cone-tracing http://research.nvidia.com/publication/interactive-indirect-... has the paper plus presentation available, plus abstract and other links.
    • wlesieutre 9y ago
      Thanks! I've replaced it with your working nvidia link. I got the citeseerx.ist.psu.edu link off google and it worked for me the first time. I'm an alum but not logged into anything, so either it was a bypass via google referrer (not sure why they'd do that, it's not looking for advertising clicks) or some usage limit.
• vaibhavsagar 9y ago
  There are a ton of fantastic Haskell papers, but if I had to pick one this would be it. It reconciles the pure and lazy functional nature of Haskell with the strict and often messy demands of the real world: State in Haskell. John Launchbury and Simon L. Peyton Jones https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/state-lasc.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
  • amelius 9y ago
    I like Haskell papers and books but they often reference the "Core" language, for which an accessible implementation seems to be lacking, which is a missed opportunity, imho. Yes, I know it is part of GHC, but it is buried under several layers of undocumented code. GHC could have been much more open to research if they modularized and documented everything more thoroughly.
    • vaibhavsagar 9y ago
      I think SPJ would agree with you. Have you seen https://www.youtube.com/watch?v=uR_VzYxvbxg https://www.youtube.com/watch?v=uR_VzYxvbxg?
• irfansharif 9y ago
  Diego Ongaro's Raft paper[1]. Perhaps this only speaks to my experience as a student but having surveyed some of the other papers in the domain (paxos[2] in its many variants: generalized paxos[3], fpaxos[4], epaxos[5], qleases[6]), I'm glad the author expended the effort he did in making Raft as understandable (relatively) as it is. [1]: https://raft.github.io/raft.pdf https://raft.github.io/raft.pdf [2]: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/paxos-simple-Copy.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [3]: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2005-33.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [4]: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2005-112.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [5]: https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf [6]: https://www.cs.cmu.edu/~dga/papers/leases-socc2014.pdf https://www.cs.cmu.edu/~dga/papers/leases-socc2014.pdf
• morphle 9y ago
  Scalability of Collaborative Environments https://sci-hub.ac/10.1109/C5.2006.32# https://sci-hub.ac/10.1109/C5.2006.32#
• mayank 9y ago
  The Flajolet-Martin paper on counting unique items in an infinite stream with constant space [1]: a great, well-written introduction to streaming algorithms that triggered my first "aha" moment in the field. You never forget your first. [1] http://algo.inria.fr/flajolet/Publications/FlMa85.pdf http://algo.inria.fr/flajolet/Publications/FlMa85.pdf
• andars 9y ago
  I'll take a broad interpretation of 'CS' and throw out a couple of personal highlights. C. Shannon, "A Symbolic Analysis of Relay and Switching Circuits" (1940): https://dspace.mit.edu/bitstream/handle/1721.1/11173/34541425-MIT.pdf?sequence=2 https://dspace.mit.edu/bitstream/handle/1721.1/11173/3454142... Shannon's master's thesis, which introduces boolean algebra to the field of digital circuit design. R.W. Hamming, "Error Detecting and Error Correcting Codes" (1950): https://ia801903.us.archive.org/1/items/bstj29-2-147/bstj29-2-147.pdf https://ia801903.us.archive.org/1/items/bstj29-2-147/bstj29-... In Hamming's own words: "Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?" J.T. Kajiya, "The Rendering Equation" (1986): http://cseweb.ucsd.edu/~ravir/274/15/papers/p143-kajiya.pdf http://cseweb.ucsd.edu/~ravir/274/15/papers/p143-kajiya.pdf Kajiya introduces the integral rendering equation, which is the basis for most current techniques of physically based rendering.
• bra-ket 9y ago
  Kanerva's Sparse Distributed Memory is quite remarkable: https://en.wikipedia.org/wiki/Sparse_distributed_memory https://en.wikipedia.org/wiki/Sparse_distributed_memory it's a book though: https://www.amazon.com/Sparse-Distributed-Memory-MIT-Press/dp/0262514699 https://www.amazon.com/Sparse-Distributed-Memory-MIT-Press/d...
• taeric 9y ago
  "Dancing Links" by Knuth (http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-col...) is still one of my favorites for my actually having understood it. :) I wish I had found it back in grade school. (Though I suspect I wouldn't have understood it, then.)
• acoravos 9y ago
  "The Moral Character of Cryptographic Work" by Phillip Rogaway Background: http://web.cs.ucdavis.edu/~rogaway/papers/moral.html http://web.cs.ucdavis.edu/~rogaway/papers/moral.html Paper: web.cs.ucdavis.edu/~rogaway/papers/moral-fn.pdf
• gens 9y ago
  "Communicating Sequential Processes" by Tony Hoare http://www.usingcsp.com/ http://www.usingcsp.com/ I read it multiple times and still don't quite understand it all. There are more great papers i read but this one comes back to mind more often then others.
• sova 9y ago
  "Collaborative creation of communal hierarchical taxonomies in social tagging systems" http://ilpubs.stanford.edu:8090/775/1/2006-10.pdf http://ilpubs.stanford.edu:8090/775/1/2006-10.pdf
• mooneater 9y ago
  "On the criteria to be used in decomposing systems into modules" by David Parnas, 1972, the seminal paper where he brings forward the key ideas that would later be called cohesion and coupling. https://www.cs.umd.edu/class/spring2003/cmsc838p/Design/criteria.pdf https://www.cs.umd.edu/class/spring2003/cmsc838p/Design/crit... Why it was important: you can't build big complex systems without these principles. Some people say he was instrumental in stopping the Star Wars program, he argued it would be impossible to test outside of war (and therefore doomed).
• atilimcetin 9y ago
  Not a single paper but Eric Veach's Ph.D. thesis 'Robust Monte Carlo Methods for Light Transport Simulation' - http://graphics.stanford.edu/papers/veach_thesis/ http://graphics.stanford.edu/papers/veach_thesis/
• zzzcpan 9y ago
  Worth mentioning Joe Armstrong's "Making reliable distributed systems in the presence of sodware errors" [1]. [1] http://erlang.org/download/armstrong_thesis_2003.pdf http://erlang.org/download/armstrong_thesis_2003.pdf
  • whateversclever 9y ago
    I was hoping your title wasn't a typo
• coherentpony 9y ago
  An Algorithm for the Machine Calculation of Complex Fourier Series James W. Cooley and John W. Tukey Mathematics of Computation Vol. 19, No. 90 (Apr., 1965), pp. 297-301 https://www.jstor.org/stable/2003354 https://www.jstor.org/stable/2003354
  • jacobolus 9y ago
    Apparently this FFT was first discovered by Gauss (1805). http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf As a follow-up, let me recommend Püschel & Moura (2006) “Algebraic Signal Processing Theory”, https://arxiv.org/pdf/cs/0612077.pdf https://arxiv.org/pdf/cs/0612077.pdf and Püschel’s other papers about similar topics. Or in a different direction, DJB (2008), “Fast multiplication and its applications”, http://cr.yp.to/lineartime/multapps-20080515.pdf http://cr.yp.to/lineartime/multapps-20080515.pdf
    • andars 9y ago
      Interesting to note that Fourier's two works were published in 1807 and 1822, so that work by Gauss also predates Fourier.
• arde 9y ago
  All of the classic papers I can think of have already been mentioned, but even though it's too recent to pass judgment a new contender may well be "Deep Learning and Quantum Entanglement: Fundamental Connections with Implications to Network Design" - https://arxiv.org/abs/1704.01552 https://arxiv.org/abs/1704.01552
  • popcorncolonel 9y ago
    Damn, did not expect to see this paper on here. When I read it, I wasn't thinking it could be listed under the "all-time favorite CS papers", but the connections are quite interesting and (retrospectively) intuitive. I'll be interested to see where/(if) it gets published.
• djhworld 9y ago
  Not hardcore CS as some of the other papers on here, but I really enjoyed the BigTable paper https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf https://static.googleusercontent.com/media/research.google.c...
• KirinDave 9y ago
  I'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/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... (if you're daunted by an 80 page paper as I am, there is also a talk on it: https://www.youtube.com/watch?v=sz9ZlZIRDAg https://www.youtube.com/watch?v=sz9ZlZIRDAg) It is possible, with some proper insight and approaches, to sort general datastructures in linear time on modern computing hardware. The speed limit of sort is O(n) with some extra constant cost (often accrued by allocation). It works by decomposing and generalizing something akin to radix sort, leveraging a composable pass of linear discriminators to do the work. There's a followup paper using this to make a very efficient in-memory database that one could easily generalize under something like kademelia and with care I suspect could make something like a better spark core. http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... I keep submitting and talking about this but no one seems to pick up on it. This paper is crazy important and every runtime environment SHOULD be scrambling to get this entire approach well-integrated into their stdlib. Unsurprisingly, Kmett has already implemented it in Haskell (it generalized neatly under the dual of the applicative+alternative functor): https://hackage.haskell.org/package/discrimination https://hackage.haskell.org/package/discrimination
  • csomar 9y ago
    Given that I'm an ignorant. Can you ELI5 like what is the impact of this? What does it change? What can you do with it on practical terms?
    • munin 9y ago
      Imagine that you make your living in a somewhat unorthodox but honest way: you live in a tent outside of the castle and every morning, as the king walks into the castle, he hands you a deck of cards. "I've just played cards last night," he says "and I'm going to again tonight, and I'd like these cards ordered and sorted by suite and number by this evening." Then the king goes into his castle and does whatever it is that kings do in castles all day. So, you take this deck of cards, which is in any old order, as the king just played with it last night, and you set about sorting it. Now, you've been doing this a long time, and your methodology has improved over the years. When you started, you would just lay the cards out in the order the king gave them to you, and then start at the beginning of the line and ask "is this card greater than the next?" and move the two cards in response to the answer so that the two are in order. You would continue this process, repeating from the beginning of the line, until you made a complete pass through the line without making any changes. Sometimes, this took you all day, sometimes you would even make the king wait for you to finish, and that made him very angry, which is very bad. Your sorting process is compounded by the limitation of your ability to read and compare the value of two cards, because you don't really know how to read or add, it takes you about ten seconds to decide if a card is greater than or less than another card. For a 52 card deck, this means your original sorting method would require 52 times 52 comparisons, or, in real time, seven and a half hours of non-stop work, leaving you no time to do anything else. Over the years of doing this job for the king you discovered some shortcuts that would take less time but still produce a sorted deck, despite your limited ability to read and understand the values of the cards. While that still takes ten seconds, your new deck sorting approaches require 52 times 1.7 comparisons, or in real time, about fifteen minutes. This is much, much, better than before, but it would of course be better still if it took even less time, as you have discovered that you can now use this extra time to sort cards for all the other members of the court. One day a traveling wizard observes you sorting cards and says "you know, this method that you have for sorting cards is quite clever but what if I were to tell you that you could sort these cards in 8.6 minutes flat?" This is about half the time it takes you right now, meaning that you could double the number of decks you sort in a day, doubling your income. You are very interested! "Tell me more," you tell the wizard. "Here, read this paper" the wizard replies, and they give you the paper GP linked.
• di4na 9y ago
  "Programming with Abstract Data Types", B Liskov and S Zilles
• CobrastanJorji 9y ago
  Yao's minimax principle. It's not a very exciting read or a very exciting conclusion compared to some of these other papers, but it's still interesting, and the conclusion has been practically useful to me a small handful of times. It concerns randomized algorithms, which are algorithms that try to overcome worst case performance by randomizing their behavior, so that a malicious user can't know which input will be the worst case input this time. The principle states that the expected cost of a randomized algorithm on a single input is no better or worse than the cost of a deterministic algorithm with random input. Yao proves this is the case by constructing two zero sum games based around the algorithms' running times and then using game theory (specifically von Neumann's minimax theorem) to show that the two approaches are equivalent. It's a really neat approach!
• hatred 9y ago
  The Byzantine Generals Problem by Lamport et al is a must read for anyone interested in distributed systems. Some of the others that have already been mentioned on this thread: - Time, Clocks, and the Ordering of Events in a Distributed System - Paxos Made Simple
• coldcode 9y ago
  Royce 1970 of course: http://www.cs.umd.edu/class/spring2003/cmsc838p/Process/waterfall.pdf http://www.cs.umd.edu/class/spring2003/cmsc838p/Process/wate... wherein he did not introduce Waterfall, but for some reason the negative aspects of his article became the basis for Waterfall. The article for 1970 is surprisingly relevant although archaic in language. It's worth reading to the end. He wrote this describing leading teams in the 1960s do what I assume was actual "rocket" science.
• btilly 9y ago
  As We May Think https://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/303881/ https://www.theatlantic.com/magazine/archive/1945/07/as-we-m... This paper, written during WW II (!) by someone who had around to 20 years of computing experience at that time (!!) introduced the world to the ideas like hypertext, and citation indexes. Google's PageRank algorithm can be seen as a recombining of ideas from this paper. This is worth reading to see how much was understood how early.
• damontal 9y ago
  the report on the Therac-25. a good warning that bugs can have very real consequences. http://sunnyday.mit.edu/papers/therac.pdf http://sunnyday.mit.edu/papers/therac.pdf
• filereaper 9y ago
  Some old ones: Jeffrey Ullman & John Hopcroft: Formal languages and their relation to automata [0] Ted Codd: A relational model of data for large shared data banks [1] C.A.R Hoare: Communicating Sequential Processes [2] [0]http://dl.acm.org/citation.cfm?id=1096945 http://dl.acm.org/citation.cfm?id=1096945 [1]http://dl.acm.org/citation.cfm?id=362685 http://dl.acm.org/citation.cfm?id=362685 [2]http://www.usingcsp.com/cspbook.pdf http://www.usingcsp.com/cspbook.pdf
• tksfz 9y ago
  Purely Functional Data Structures by Chris Okasaki - https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf Can programming be liberated from the von Neumann style? - John Backus's Turing lecture - http://dl.acm.org/citation.cfm?id=1283933 http://dl.acm.org/citation.cfm?id=1283933
• ddebernardy 9y ago
  Knuth vs Email: http://www-cs-faculty.stanford.edu/~knuth/email.html http://www-cs-faculty.stanford.edu/~knuth/email.html It's not technically a CS paper, but well worth the (very short) read regardless.
• kendallpark 9y ago
  I'm surprised no one has mentioned "The Cathedral and the Bazaar" yet. Admittedly is more essay, less paper. https://en.wikipedia.org/wiki/The_Cathedral_and_the_Bazaar https://en.wikipedia.org/wiki/The_Cathedral_and_the_Bazaar
• totalZero 9y ago
  Intelligence without representation, by Rodney Brooks. http://people.csail.mit.edu/brooks/papers/representation.pdf http://people.csail.mit.edu/brooks/papers/representation.pdf
• kageneko 9y ago
  Oh man... I don't know. There's so many. I'll need to go with Gilbert, E., & Karahalios, K. (2009, April). Predicting tie strength with social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (pp. 211-220). ACM. In grad school, it was the paper that kept on giving. I think I cited it every semester for a paper or project. There's a lot of other papers and books that really inspired me, but this one was magic.
• dansto 9y ago
  PCP theorem as explained by Bernard Chazelle , 2001 https://www.cs.princeton.edu/~chazelle/pubs/bourbaki.pdf https://www.cs.princeton.edu/~chazelle/pubs/bourbaki.pdf Great writing style!
• vsrinivas 9y ago
  From the perspective of - 'take a fresh look at something we take for granted' - "A Preliminary Architecture for a Basic Data-Flow Processor" (Dennis & Misunas 1975) Focusing on the flow of data between operators and greedily executing a linear program is what an out-of-order processor is.
• deleted 9y ago
  [deleted]
• chowells 9y ago
  The Essence of the Iterator Pattern, by Gibbons and Oliveira. This paper develops a precise model for internal iteration of a data structure, such that exactly the necessary information is exposed and no more. It's a fantastic exploration of improving a well-known design space with justified removal of details. I keep its lessons in mind whenever I am facing code that seems to have a lot of incidental complexity. https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator...
• mrlyc 9y ago
  My favourite is "Targeting Safety-Related Errors During Software Requirements Analysis" by Robyn Lutz at the Jet Propulsion Laboratory. It's available at https://trs.jpl.nasa.gov/bitstream/handle/2014/35179/93-0749.pdf https://trs.jpl.nasa.gov/bitstream/handle/2014/35179/93-0749... The article provides a safety checklist for use during the analysis of software requirements for spacecraft and other safety-critical, embedded systems.
• ratsimihah 9y ago
  Deepmind's first paper on deep reinforcement learning. The beginning of a new era towards AGI : ) Human-level control through deep reinforcement learning http://www.nature.com/nature/journal/v518/n7540/full/nature14236.html?foxtrotcallback=true http://www.nature.com/nature/journal/v518/n7540/full/nature1...
• baddox 9y ago
  Scott Aaronson's "Why Philosophers Should Care About Computational Complexity" https://www.scottaaronson.com/papers/philos.pdf https://www.scottaaronson.com/papers/philos.pdf
• 505 9y ago
  I see some of my favourites among other replies. I don't think I see these: http://aegis.sourceforge.net/auug97.pdf http://aegis.sourceforge.net/auug97.pdf http://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf http://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf
• protomyth 9y ago
  I 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 http://cife.stanford.edu/node/599 2) 1993 http://faculty.cs.tamu.edu/ioerger/cs631-fall05/AOP.pdf http://faculty.cs.tamu.edu/ioerger/cs631-fall05/AOP.pdf
• chajath 9y ago
  Delegation is Inheritance http://wiki.c2.com/?DelegationIsInheritance http://wiki.c2.com/?DelegationIsInheritance
• probinso 9y ago
  Relevance Vector Machines by Tipping or Homomorphic Encryption over the Integers
• jonbaer 9y ago
  Anything dealing w/ "reversible computing", makes you ask "what-if" ... http://cqi.inf.usi.ch/qic/80_Toffoli.pdf http://cqi.inf.usi.ch/qic/80_Toffoli.pdf https://www.eng.famu.fsu.edu/~mpf/Frank-99-PhD-bookmarked.pdf https://www.eng.famu.fsu.edu/~mpf/Frank-99-PhD-bookmarked.pd...
• phamilton 9y ago
  The Dynamo Paper. http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf http://www.allthingsdistributed.com/files/amazon-dynamo-sosp... One of the best practical "How can this improve our business?" technical papers, and an excellent introduction to reading papers.
• p4bl0 9y ago
  It's not exactly a paper but I really liked "The Limits of Mathematics" by Chaitin. I wrote a blogpost about it a few years back (https://shebang.ws/the-limits-of-mathematics.html https://shebang.ws/the-limits-of-mathematics.html), I already submitted it to HN (https://news.ycombinator.com/item?id=1725936 https://news.ycombinator.com/item?id=1725936).
• surement 9y ago
  The splay trees paper by Sleator and Tarjan (1985) https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf It's just such a cool result and the paper is very well written. Further, the dynamic optimality conjecture at the end is still an open problem.
• Rickasaurus 9y ago
  "NP-complete Problems and Physical Reality" by Scott Aaronson. It relates NP-complete problems to examples in nature. Excellent paper and a fun read. https://arxiv.org/abs/quant-ph/0502072 https://arxiv.org/abs/quant-ph/0502072
• kruhft 9y ago
  On Formally Undecidable Propositions... by Kurt Godel. One might argue this is not CS, but it's something everyone should read and understand.
• kwindla 9y ago
  Alexia Massalin’s 1992 PhD thesis describing the Synthesis Operating System. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.4871&rep=rep1&type=pdf Here's Valerie Aurora’s description of Synthesis: ... a completely lock-free operating system optimized using run-time code generation, written from scratch in assembly running on a homemade two-CPU SMP with a two-word compare-and-swap instruction — you know, nothing fancy. Which (necessarily) undersells by a very large margin just how impressive, innovative, and interesting this thesis is. If you’re interested in operating systems, or compilers, or concurrency, or data structures, or real-time programming, or benchmarking, or optimization, you should read this thesis. Twenty-five years after it was published, it still provides a wealth of general inspiration and specific food for thought. It’s also clearly and elegantly written. And, as a final bonus, it’s a snapshot from an era in which Sony made workstations and shipped its own, proprietary, version of Unix. Good times.
• haihaibye 9y ago
  Why it is Important that Software Projects Fail http://berglas.org/Articles/ImportantThatSoftwareFails/ImportantThatSoftwareFails.html http://berglas.org/Articles/ImportantThatSoftwareFails/Impor...
• codelord 9y ago
  ImageNet Classification with Deep Convolutional Neural Networks https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf https://papers.nips.cc/paper/4824-imagenet-classification-wi... If not evident already, time will tell that this paper brought us to a new era.
• cjbprime 9y ago
  I'll go with an unconventional choice: Michael Kleber's _The Best Card Trick_: http://www.northeastern.edu/seigen/11Magic/Articles/Best%20Card%20Trick.pdf http://www.northeastern.edu/seigen/11Magic/Articles/Best%20C...
• uvatbc 9y ago
  One of my all time favorites has been the Jefferey Mogul paper on Receive Livelock: https://pdos.csail.mit.edu/6.828/2008/readings/mogul96usenix.pdf https://pdos.csail.mit.edu/6.828/2008/readings/mogul96usenix... I read it first as a normal CS paper, but later started seeing it as a commentary on an extremely busy work life. Right there in the first paragraph: "... receive livelock, in which the system spends all its time processing interrupts, to the exclusion of other tasks..." Does this remind you of anything?
• johnny_1010 9y ago
  Communicating Sequential Processes C. A. R. Hoare http://www.usingcsp.com/cspbook.pdf http://www.usingcsp.com/cspbook.pdf
• GeorgeTirebiter 9y ago
  "Hints for Computer System Design" by Butler Lampson https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/acrobat-17.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
• Frogolocalypse 9y ago
  The bitcoin whitepaper. https://bitcoin.org/bitcoin.pdf https://bitcoin.org/bitcoin.pdf
• megahz 9y ago
  http://insecure.org/stf/smashstack.html http://insecure.org/stf/smashstack.html
• megahz 9y ago
  Smashing the stack for fun adn profit http://insecure.org/stf/smashstack.html http://insecure.org/stf/smashstack.html
• dkamm 9y ago
  "On non-computable functions" - Tibor Rado. Proof that the busy beaver function is not computable. http://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf http://computation4cognitivescientists.weebly.com/uploads/6/...
• mathgenius 9y ago
  "The Derivative of a Regular Type is its Type of One-Hole Contexts" - Conor McBride, http://strictlypositive.org/diff.pdf http://strictlypositive.org/diff.pdf This shows how you end up "differentiating" datatypes in the context of strict functional programming, in order to do things like "mutate" lists. It is essentially the same as what mathematicians call "combinatorial species".
• dharness 9y ago
  Seam Carving! http://perso.crans.org/frenoy/matlab2012/seamcarving.pdf http://perso.crans.org/frenoy/matlab2012/seamcarving.pdf
• rahulmehta95 9y ago
  Trading Group Theory for Randomness by Laci Babai (http://dl.acm.org/citation.cfm?id=22192 http://dl.acm.org/citation.cfm?id=22192) -- this beautiful paper introduced algorithmic group theory & interactive proofs (in the form of Arthur-Merlin games) to study the Graph Isomorphism problem, and introduced several groundbreaking new results. Perhaps a more approachable (and funny) version of this would be Babai's humorous essay detailing the flurry of work that broke out after his results introducing AM/MA...it's the closest thing I've seen to making theoretical CS exhilarating :P (http://www.cs.princeton.edu/courses/archive/spr09/cos522/BabaiEmail.pdf http://www.cs.princeton.edu/courses/archive/spr09/cos522/Bab...)
• archagon 9y ago
  I haven't read a ton of academic research in general, but in trying to understand CRDTs and concurrency, gritzko's paper on "Causal Trees"[1] struck me as incredibly smart and clear in its thinking. Many of the other CRDT papers I read (even influential ones) were flawed in a number of respects: blurred lines between design and implementation, blatant mistakes and typos, hasty and unconvincing conclusions, an overabundance of newly-minted terms and acronyms, dense proofs lacking any concrete examples, unintuitive divisions between operation history and state mutation. The Causal Trees paper is also dense and also invents a bunch of new vocabulary, but the logic is completely consistent (to the point of being unified under a single metaphor) and clearly explained every step of the way. The data format is also very clever, and the paper spends a good amount of time following the practical consequences of those design decisions, e.g. the ease of displaying inline changes, or of generating a particular revision of the document. Weirdly, the paper isn't much discussed alongside the usual contenders. (WOOT, Logoot, RGA, LSEQ, etc.) [1]: https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b6dc19f4fd529caab43.pdf https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b...
• rurban 9y ago
  "Cache-Conscious Collision Resolution in String Hash Tables" Nikolas Askitis and Justin Zobel, SPIRE 2005 The most simple and most effective hash table scheme, and nobody is using it, or even knows about it. Fastest and least memory, but not thread-safe. After 12 years there's still nothing better on the horizon. Though the CheneyMTA paper is also brilliant, a typical Baker paper.
• ddrsurvivor 9y ago
  I know this doesn't really count, but the "Get me off your fucking mailing list" one made me giggle - http://www.scs.stanford.edu/~dm/home/papers/remove.pdf http://www.scs.stanford.edu/~dm/home/papers/remove.pdf