Algorithms to Live By

by Brian Christian

  Gallagher, P., and C. Kerry. Digital Signature Standard. FIPS PUB 186-4, 2013.

  Garey, Michael R., and David S. Johnson. Computers and Intractability: A Guide to NP-Completeness. New York: W. H. Freeman, 1979.

  Garfield, Eugene. “Recognizing the Role of Chance.” Scientist 2, no. 8 (1988): 10.

  Garrett, A. J. M., and P. Coles. “Bayesian Inductive Inference and the Anthropic Cosmological Principle.” Comments on Astrophysics. 17 (1993): 23–47.

  Gasarch, William I. “The P =? NP Poll.” SIGACT News 33, no. 2 (2002): 34–47.

  Gauthier, David P. Morals by Agreement. New York: Oxford University Press, 1985.

  Geman, Stuart, Elie Bienenstock, and René Doursat. “Neural Networks and the Bias/Variance Dilemma.” Neural Computation 4, no. 1 (1992): 1–58.

  Geoffrion, Arthur M. “Lagrangean Relaxation for Integer Programming.” Mathematical Programming Study 2 (1974): 82–114.

  ______. “Lagrangian Relaxation for Integer Programming.” In 50 Years of Integer Programming 1958–2008: From Early Years to State of the Art. Edited by Michael Juenger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey. Berlin: Springer, 2010, 243–281.

  Gigerenzer, Gerd, and Henry Brighton. “Homo Heuristicus: Why Biased Minds Make Better Inferences.” Topics in Cognitive Science 1, no. 1 (2009): 107–143.

  Gilbert, Daniel. Stumbling on Happiness. New York: Knopf, 2006.

  Gilbert, John P. and Frederick Mosteller. “Recognizing the Maximum of a Sequence.” Journal of the American Statistical Association 61 (1966): 35–75.

  Gilboa, Itzhak, and Eitan Zemel. “Nash and Correlated Equilibria: Some Complexity Considerations.” Games and Economic Behavior 1, no. 1 (1989): 80–93.

  Gillispie, Charles Coulston. Pierre-Simon Laplace, 1749–1827: A Life in Exact Science. Princeton, NJ: Princeton University Press, 2000.

  Gilmore, Paul C., and Ralph E. Gomory. “A Linear Programming Approach to the Cutting Stock Problem, Part II.” Operations Research 11, no. 6 (1963): 863–888.

  Gilovich, Thomas. How We Know What Isn’t So. New York: Simon & Schuster, 2008.

  Ginsberg, Allen. Howl and Other Poems. San Francisco: City Lights Books, 1956.

  Gittins, John C. “Bandit Processes and Dynamic Allocation Indices.” Journal of the Royal Statistical Society, Series B (Methodological) 41 (1979): 148–177.

  Gittins, John C., Kevin Glazebrook, and Richard Weber. Multi-Armed Bandit Allocation Indices, 2nd ed. Chichester, UK: Wiley, 2011.

  Gittins, John C., and D. Jones. “A Dynamic Allocation Index for the Sequential Design of Experiments.” In Progress in Statistics. Amsterdam: North Holland, 1974, 241–266.

  Glassner, Barry. “Narrative Techniques of Fear Mongering.” Social Research 71 (2004): 819–826.

  Goldberg, Paul W., and Christos H. Papadimitriou. “Reducibility Between Equilibrium Problems.” ACM Symposium on Theory of Computing 2006, 62–70.

  Good, Irving John. Good Thinking: The Foundations of Probability and Its Applications. Minneapolis, MN: University of Minnesota Press, 1983.

  Gopnik, Alison, Andrew N. Meltzoff, and Patricia K. Kuhl. The Scientist in the Crib. New York: Morrow, 1999.

  Gordon, Deborah M. “Control Without Hierarchy.” Nature 446, no. 7132 (2007): 143.

  Gott, J. R. “Future Prospects Discussed.” Nature 368 (1994): 108.

  ______. “Implications of the Copernican Principle for Our Future Prospects.” Nature 363 (1993): 315–319.

  Gould, Stephen Jay. “The Median Isn’t the Message.” Discover 6, no. 6 (1985): 40–42.

  Graham, Ronald L., Eugene L. Lawler, Jan Karel Lenstra, and Alexander H. G. Rinnooy Kan. “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey.” Annals of Discrete Mathematics 5 (1979): 287–326.

  Grenander, Ulf. “On Empirical Spectral Analysis of Stochastic Processes.” Arkiv för Matematik 1, no. 6 (1952): 503–531.

  Gridgeman, T. “Geometric Probability and the Number π.” Scripta Mathematika 25, no. 3 (1960): 183–195.

  Griffiths, Thomas L., Charles Kemp, and Joshua B. Tenenbaum. “Bayesian Models of Cognition.” In The Cambridge Handbook of Computational Cognitive Modeling. Edited by Ron Sun. Cambridge, UK: Cambridge University Press, 2008.

  Griffiths, Thomas L., Falk Lieder, and Noah D. Goodman. “Rational Use of Cognitive Resources: Levels of Analysis Between the Computational and the Algorithmic.” Topics in Cognitive Science 7 (2015): 217–229.

  Griffiths, Thomas L., David M. Sobel, Joshua B. Tenenbaum, and Alison Gopnik. “Bayes and Blickets: Effects of Knowledge on Causal Induction in Children and Adults.” Cognitive Science 35 (2011): 1407–1455.

  Griffiths, Thomas L., Mark Steyvers, and Alana Firl. “Google and the Mind: Predicting Fluency with PageRank.” Psychological Science 18 (2007): 1069–1076.

  Griffiths, Thomas L., and Joshua B. Tenenbaum. “Optimal Predictions in Everyday Cognition.” Psychological Science 17 (2006): 767–773.

  Grossman, Dave, and L. W. Christensen. On Combat. Belleville, IL: PPCT Research Publications, 2004.

  Haggstrom, Gus W. “Optimal Sequential Procedures When More Than One Stop Is Required.” Annals of Mathematical Statistics 38 (1967): 1618–1626.

  Halevy, Alon, Peter Norvig, and Fernando Pereira. “The Unreasonable Effectiveness of Data.” Intelligent Systems, IEEE 24, no. 2 (2009): 8–12.

  Hardin, Garrett. “The Tragedy of the Commons.” Science 162, no. 3859 (1968): 1243–1248.

  Hardy, G. H. Collected Works. Vol. II. Oxford, UK: Oxford University Press, 1967.

  ______. “Prime Numbers.” British Association Report 10 (1915): 350–354.

  Harmenberg, J. Epee 2.0: The Birth of the New Fencing Paradigm. New York: SKA Swordplay Books, 2007.

  Harsanyi, John C. “Can the Maximin Principle Serve as a Basis for Morality? A Critique of John Rawls’s Theory.” The American Political Science Review 69, no. 2 (1975): 594–606.

  Harvey, Jerry B. “The Abilene Paradox: The Management of Agreement.” Organizational Dynamics 3, no. 1 (1974): 63–80.

  Hastings, W. K. “Monte Carlo Methods Using Markov Chains and Their Applications.” Biometrika 57 (1970): 97–109.

  Hawken, Angela, and Mark Kleiman. Managing Drug Involved Probationers with Swift and Certain Sanctions: Evaluating Hawaii’s HOPE. Report submitted to the National Institute of Justice. 2009. http://www.ncjrs.gov/pdffiles1/nij/grants/229023.pdf.

  Held, Michael, and Richard M. Karp. “The Traveling-Salesman Problem and Minimum Spanning Trees.” Operations Research 18, no. 6 (1970): 1138–1162.

  ______. “The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.” Mathematical Programming 1, no. 1 (1971): 6–25.

  Henderson, T. Discrete Relaxation Techniques. Oxford, UK: Oxford University Press, 1989.

  Hennessy, John L., and David A. Patterson. Computer Architecture: A Quantitative Approach. New York: Elsevier, 2012.

  Herrmann, Jeffrey W. “The Perspectives of Taylor, Gantt, and Johnson: How to Improve Production Scheduling.” International Journal of Operations and Quality Management 16 (2010): 243–254.

  Heyde, C. C. “Agner Krarup Erlang.” In Statisticians of the Centuries. Edited by C. C. Heyde, E. Seneta, P. Crepel, S. E. Fienberg, and J. Gani, 328–330. New York: Springer, 2001.

  Hill, Theodore. “Knowing When to Stop.” American Scientist 97 (2009): 126–131.

  Hillis, W. Daniel. The Pattern on the Stone: The Simple Ideas That Make Computers Work. New York: Basic Books, 1998.

  Hirshleifer, Jack. “On the Emotions as Guarantors of Threats and Promises.” In The Latest on the Best: Essays in Evolution and Optimality. Edited by John Dupre, 307–326. Cambridge, MA: MIT Press, 1987.

  Hoffman, David. The Oligarchs: Wealth and Power in the New Russia. New York: PublicAffairs, 2003.

  Horvitz, Eric, and Shlomo Zilberstein. “Computational Tradeoffs Under Bounded Resources.” Artificial In
telligence 126 (2001): 1–4.

  Hosken, James C. “Evaluation of Sorting Methods.” In Papers and Discussions Presented at the November 7–9, 1955, Eastern Joint AIEE-IRE Computer Conference: Computers in Business and Industrial Systems, 39–55.

  Hurd, Cuthbert C. “A Note on Early Monte Carlo Computations and Scientific Meetings.” IEEE Annals of the History of Computing 7, no. 2 (1985): 141–155.

  Impagliazzo, Russell, and Avi Wigderson. “P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.” In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997, 220–229.

  ______. “Randomness vs. Time: De-Randomization Under a Uniform Assumption.” In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, 734–743.

  Ingram, Wendy Marie, Leeanne M. Goodrich, Ellen A. Robey, and Michael B. Eisen. “Mice Infected with Low-Virulence Strains of Toxoplasma Gondii Lose Their Innate Aversion to Cat Urine, Even After Extensive Parasite Clearance.” PLOS ONE, no. 9 (2013): e75246.

  Jackson, James R. Scheduling a Production Line to Minimize Maximum Tardiness. Technical report 43. Management Science Research Project, University of California, Los Angeles, 1955.

  Jacobson, Van. “Congestion Avoidance and Control.” In ACM SIGCOMM Computer Communication Review 18, no. 4 (1988): 314–329.

  ______. “A New Way to Look at Networking.” Lecture at Google, Mountain View, CA, August 2006. https://www.youtube.com/watch?v=oCZMoY3q2uM.

  James, William. “Great Men, Great Thoughts, and the Environment.” Atlantic Monthly 46 (1880): 441–459.

  ______. Psychology: Briefer Course. New York: Holt, 1892.

  Jay, Francine. The Joy of Less: A Minimalist Living Guide: How to Declutter, Organize, and Simplify Your Life. Medford, NJ: Anja Press, 2010.

  Jeffreys, Harold. “An Invariant Form for the Prior Probability in Estimation Problems.” Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 186 (1946): 453–461.

  ______. Theory of Probability, 3rd ed. Oxford, UK: Oxford University Press, 1961.

  Johnson, Selmer Martin. “Optimal Two- and Three-Stage Production Schedules with Setup Times Included.” Naval Research Logistics Quarterly 1, no. 1 (1954): 61–68.

  Johnson, Theodore, and Dennis Shasha. “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm.” VLDB ’94 Proceedings of the 20th International Conference on Very Large Data Bases, 1994, 439–450.

  Jones, Thomas B., and David H. Ackley. “Comparison Criticality in Sorting Algorithms.” In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), June 2014, 726–731.

  Jones, William. Keeping Found Things Found: The Study and Practice of Personal Information Management. Burlington, MA: Morgan Kaufmann, 2007.

  Kaelbling, Leslie Pack. Learning in Embedded Systems. Cambrige, MA: MIT Press, 1993.

  Kaelbling, Leslie Pack, Michael L. Littman, and Andrew W. Moore. “Reinforcement Learning: A Survey.” Journal of Artificial Intelligence Research 4 (1996): 237–285.

  Kanigel, Robert. The One Best Way: Frederick Winslow Taylor and the Enigma of Efficiency. New York: Viking Penguin, 1997.

  Kant, Immanuel. Grundlegung zur Metaphysik der Sitten. Riga: Johann Friedrich Hartknoch, 1785.

  ______. Kritik der praktischen Vernunft. Riga: Johann Friedrich Hartknoch, 1788.

  Karmarkar, Narendra. “A New Polynomial-Time Algorithm for Linear Programming.” In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, 1984, 302–311.

  Karp, Richard M. “An Introduction to Randomized Algorithms.” Discrete Applied Mathematics 34, no. 1 (1991): 165–201.

  ______. “Reducibility Among Combinatorial Problems.” In Complexity of Computer Computations, 85–103. New York: Plenum, 1972.

  Katajainen, Jyrki, and Jesper Larsson Träff. “A Meticulous Analysis of Mergesort Programs.” In Algorithms and Complexity: Third Italian Conference CIAC ’97. Berlin: Springer, 1997.

  Katehakis, Michael N., and Herbert Robbins. “Sequential Choice from Several Populations.” Proceedings of the National Academy of Sciences 92 (1995): 8584–8585.

  Kelly, F. P. “Multi-Armed Bandits with Discount Factor Near One: The Bernoulli Case.” Annals of Statistics 9 (1981): 987–1001.

  Kelly, John L. “A New Interpretation of Information Rate.” Information Theory, IRE Transactions on 2, no. 3 (1956): 185–189.

  Khachiyan, Leonid G. “Polynomial Algorithms in Linear Programming.” USSR Computational Mathematics and Mathematical Physics 20, no. 1 (1980): 53–72.

  Khot, Subhash, and Oded Regev. “Vertex Cover Might Be Hard to Approximate to Within 2-ε.” Journal of Computer and System Sciences 74, no. 3 (2008): 335–349.

  Kidd, Celeste, Holly Palmeri, and Richard N. Aslin. “Rational Snacking: Young Children’s Decision-Making on the Marshmallow Task Is Moderated by Beliefs About Environmental Reliability.” Cognition 126, no. 1 (2013): 109–114.

  Kilburn, Tom, David B. G. Edwards, M. J. Lanigan, and Frank H. Sumner. “One-Level Storage System.” IRE Transactions on Electronic Computers (1962): 223–235.

  Kinsbourne, Marcel. “Somatic Twist: A Model for the Evolution of Decussation.” Neuropsychology 27, no. 5 (2013): 511.

  Kirby, Kris N. “Bidding on the Future: Evidence Against Normative Discounting of Delayed Rewards.” Journal of Experimental Psychology: General 126, no. 1 (1997): 54–70.

  Kirkpatrick, Scott, C. D. Gelatt, and M. P. Vecchi. “Optimization by Simulated Annealing.” Science 220, no. 4598 (1983): 671–680.

  Knuth, Donald E. “Ancient Babylonian Algorithms.” Communications of the ACM 15, no. 7 (1972): 671–677.

  ______. The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed. Boston: Addison-Wesley, 1997.

  ______. The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd ed. Boston: Addison-Wesley, 1997.

  ______. “A Terminological Proposal.” ACM SIGACT News 6, no. 1 (1974): 12–18.

  ______. “The TeX Tuneup of 2014.” TUGboat 35, no. 1 (2014).

  ______. Things a Computer Scientist Rarely Talks About. Stanford, CA: Center for the Study of Language/Information, 2001.

  ______. “Von Neumann’s First Computer Program.” ACM Computing Surveys (CSUR) 2, no. 4 (December 1970): 247–260.

  Koestler, Arthur. The Watershed: A Biography of Johannes Kepler. Garden City, NY: Doubleday, 1960.

  Kozen, Dexter, and Shmuel Zaks. “Optimal Bounds for the Change-Making Problem.” In Automata, Languages and Programming, 700: 150–161. Edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson. Berlin: Springer, 1993.

  Lai, Tze Leung, and Herbert Robbins. “Asymptotically Efficient Adaptive Allocation Rules.” Advances in Applied Mathematics 6 (1985): 4–22.

  Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine Generals Problem.” ACM Transactions on Programming Languages and Systems (TOPLAS) 4, no. 3 (1982): 382–401.

  Laplace, Pierre-Simon. A Philosophical Essay on Probabilities. 1812. Reprint, New York: Dover, 1951.

  ______. “Memoir on the Probability of the Causes of Events.” Statistical Science 1 (1774/1986): 364–378.

  ______. Théorie analytique des probabilités. Paris: Mme Ve Courcier, 1812.

  Lawler, Eugene L. “Old Stories.” In History of Mathematical Programming. A Collection of Personal Reminiscences, 97–106. Amsterdam: CWI/North-Holland, 1991.

  ______. “Optimal Sequencing of a Single Machine Subject to Precedence Constraints.” Management Science 19, no. 5 (1973): 544–546.

  ______. Scheduling a Single Machine to Minimize the Number of Late Jobs. Technical report. Berkeley: University of California, 1983.

  ______. “Scheduling a Single Machine to Minimize the Number of Late Jobs,” no. UCB/CSD-83-139 (1983). http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6344.html.

  ______. “Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedenc
e Constraints.” Annals of Discrete Mathematics 2 (1978): 75–90.

  Lawler, Eugene L., Jan Karel Lenstra, and Alexander H. G. Rinnooy Kan. “A Gift for Alexander!: At Play in the Fields of Scheduling Theory.” Optima 7 (1982): 1–3.

  Lawler, Eugene L., Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys. “Sequencing and Scheduling: Algorithms and Complexity.” In Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory, edited by S. S. Graves, A. H. G. Rinnooy Kan, and P. Zipkin, 445–522. Amsterdam: North Holland, 1993.

  ______. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York: Wiley, 1985.

  Lazzarini, Mario. “Un’applicazione del calcolo della probabilità alla ricerca sperimentale di un valore approssimato di π.” Periodico di Matematica 4 (1901): 140–143.

  Lee, Donghee, S. H. Noh, S. L. Min, J. Choi, J. H. Kim, Yookun Cho, and Chong Sang Kim. “LRFU: A Spectrum of Policies That Subsumes the Least Recently Used and Least Frequently Used Policies.” IEEE Transactions on Computers 50 (2001): 1352–1361.

  Le Guin, Ursula K. “The Ones Who Walk Away from Omelas.” In New Dimensions 3. Edited by Robert Silverberg. New York: Signet, 1973.

  Lenstra, Jan Karel. “The Mystical Power of Twoness: In Memoriam Eugene L. Lawler.” Journal of Scheduling 1, no. 1 (1998): 3–14.

  Lenstra, Jan Karel, Alexander H. G. Rinnooy Kan, and Peter Brucker. “Complexity of Machine Scheduling Problems.” Annals of Discrete Mathematics 1 (1977): 343–362.

  Lerner, Ben. The Lichtenberg Figures. Port Townsend, WA: Copper Canyon Press, 2004.

  Lindley, Denis V. “Dynamic Programming and Decision Theory.” Applied Statistics 10 (1961): 39–51.

  Lippman, Steven A., and John J. McCall. “The Economics of Job Search: A Survey.” Economic Inquiry 14 (1976): 155–189.

  Lorie, James H., and Leonard J. Savage. “Three Problems in Rationing Capital.” Journal of Business 28, no. 4 (1955): 229–239.

  Lowe, Christopher J., Mark Terasaki, Michael Wu, Robert M. Freeman Jr., Linda Runft, Kristen Kwan, Saori Haigo, Jochanan Aronowicz, Eric Lander, Chris Gruber, et al. “Dorsoventral Patterning in Hemichordates: Insights into Early Chordate Evolution.” PLoS Biology 4, no. 9 (2006): e291.