31 results back to index
The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow
Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Donald Knuth, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, Johannes Kepler, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Rubik’s Cube, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam
All Rights Reserved Library of Congress Cataloging-in-Publication Data Fortnow, Lance, 1963– The golden ticket : P, NP, and the search for the impossible / Lance Fortnow. pages cm Summary: “The P-NP problem is the most important open problem in computer science, if not all of mathematics. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook.
The most prestigious computer science journal receives a steady stream of papers claiming to resolve the P versus NP question and has a specific policy for those papers: The Journal of the ACM frequently receives submissions purporting to solve a long-standing open problem in complexity theory, such as the P/NP problem. Such submissions tax the voluntary editorial and peer-reviewing resources used by JACM, by requiring the review process to identify the errors in them. JACM remains open to the possibility of eventual resolution of P/NP and related questions, and continues to welcome submissions on the subject. However, to mitigate the burden of repeated resubmissions of incremental corrections of errors identified during editorial review, JACM has adopted the following policy: No author may submit more than one paper on the P/NP or related long-standing questions in complexity theory in any 24 month period, except by invitation of the Editor-in-Chief. This applies to resubmissions of previously rejected manuscripts.
THE GOLDEN TICKET THE GOLDEN TICKET P, NP, AND THE SEARCH FOR THE IMPOSSIBLE LANCE FORTNOW PRINCETON UNIVERSITY PRESS PRINCETON AND OXFORD Copyright © 2013 by Princeton University Press Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540 In the United Kingdom: Princeton University Press, 6 Oxford Street, Woodstock, Oxfordshire OX20 1TW press.princeton.edu The epigraph for this book is taken from Charlie and the Chocolate Factory by Roald Dahl, copyright © 1964, renewed 1992 by Roald Dahl Nominee Limited. Used by permission of Alfred A. Knopf, an imprint of Random House Children’s Books, a division of Random House, Inc. Any third party use of this material, outside of this publication, is prohibited. Interested parties must apply directly to Random House, Inc. for permission.
The Simpsons and Their Mathematical Secrets by Simon Singh
Albert Einstein, Andrew Wiles, Benoit Mandelbrot, cognitive dissonance, Donald Knuth, Erdős number, Georg Cantor, Grace Hopper, Isaac Newton, John Nash: game theory, Kickstarter, mandelbrot fractal, Menlo Park, Norbert Wiener, Norman Mailer, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, Richard Feynman, Rubik’s Cube, Schrödinger's Cat, Simon Singh, Stephen Hawking, Wolfskehl Prize, women in the workforce
Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths
4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Bayesian statistics, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, David Heinemeier Hansson, delayed gratification, dematerialisation, diversification, Donald Knuth, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, Johannes Kepler, John Nash: game theory, John von Neumann, Kickstarter, knapsack problem, Lao Tzu, Leonard Kleinrock, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, Pierre-Simon Laplace, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, Sam Altman, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Stanford marshmallow experiment, Steve Jobs, stochastic process, Thomas Bayes, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Vilfredo Pareto, Walter Mischel, Y Combinator, zero-sum game
(In “A Terminological Proposal,” Donald Knuth suggested this as an appropriate label for NP-hard problems, in addition to offering a live turkey to anybody who could prove P = NP.) The intractable scheduling problems that Eugene Lawler encountered in chapter 5 fall into this category. An NP-hard problem that is itself in NP is known as “NP-complete.” See Karp, “Reducibility Among Combinatorial Problems,” for the classic result showing that a version of the traveling salesman problem is NP-complete, and Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, for an accessible introduction to P and NP. most computer scientists believe that there aren’t any: In a 2002 survey of one hundred leading theoretical computer scientists, sixty-one thought P ≠ NP and only nine thought P = NP (Gasarch, “The P =? NP Poll”). While proving P = NP could be done by exhibiting a polynomial-time algorithm for an NP-complete problem, proving P ≠ NP requires making complex arguments about the limits of polynomial-time algorithms, and there wasn’t much agreement among the people surveyed about exactly what kind of mathematics will be needed to solve this problem.
______. “Some Experimental Games.” In Research Memorandum RM-789. Santa Monica, CA: RAND, 1952. ______. “The Traveling-Salesman Problem.” Operations Research 4, no. 1 (1956): 61–75. ______. “What Future Is There for Intelligent Machines?” Audio Visual Communication Review 11, no. 6 (1963): 260–270. Forster, Edward M. Howards End. London: Edward Arnold, 1910. Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press, 2013. Fraker, Guy C. “The Real Lincoln Highway: The Forgotten Lincoln Circuit Markers.” Journal of the Abraham Lincoln Association 25 (2004): 76–97. Frank, Robert H. “If Homo Economicus Could Choose His Own Utility Function, Would He Want One with a Conscience?” American Economic Review 1987, 593–604. ______. Passions within Reason: The Strategic Role of the Emotions.
The Half-Life of Facts: Why Everything We Know Has an Expiration Date by Samuel Arbesman
Albert Einstein, Alfred Russel Wallace, Amazon Mechanical Turk, Andrew Wiles, bioinformatics, British Empire, Cesare Marchetti: Marchetti’s constant, Chelsea Manning, Clayton Christensen, cognitive bias, cognitive dissonance, conceptual framework, David Brooks, demographic transition, double entry bookkeeping, double helix, Galaxy Zoo, guest worker program, Gödel, Escher, Bach, Ignaz Semmelweis: hand washing, index fund, invention of movable type, Isaac Newton, John Harrison: Longitude, Kevin Kelly, life extension, Marc Andreessen, meta analysis, meta-analysis, Milgram experiment, Nicholas Carr, P = NP, p-value, Paul Erdős, Pluto: dwarf planet, publication bias, randomized controlled trial, Richard Feynman, Rodney Brooks, scientific worldview, social graph, social web, text mining, the scientific method, Thomas Kuhn: the structure of scientific revolutions, Thomas Malthus, Tyler Cowen: Great Stagnation
Natural language processing with Python by Steven Bird, Ewan Klein, Edward Loper
bioinformatics, business intelligence, conceptual framework, Donald Knuth, elephant in my pajamas, en.wikipedia.org, finite state, Firefox, Guido van Rossum, information retrieval, Menlo Park, natural language processing, P = NP, search inside the book, speech recognition, statistical model, text mining, Turing test
Mary’s intelligence impressed her teachers The simplified noun tags are N for common nouns like book, and NP for proper nouns like Scotland. 184 | Chapter 5: Categorizing and Tagging Words Let’s inspect some tagged text to see what parts-of-speech occur before a noun, with the most frequent ones first. To begin with, we construct a list of bigrams whose members are themselves word-tag pairs, such as (('The', 'DET'), ('Fulton', 'NP')) and (('Fulton', 'NP'), ('County', 'N')). Then we construct a FreqDist from the tag parts of the bigrams. >>> word_tag_pairs = nltk.bigrams(brown_news_tagged) >>> list(nltk.FreqDist(a for (a, b) in word_tag_pairs if b == 'N')) ['DET', 'ADJ', 'N', 'P', 'NP', 'NUM', 'V', 'PRO', 'CNJ', '.', ',', 'VG', 'VN', ...] This confirms our assertion that nouns occur after determiners and adjectives, including numeral adjectives (tagged as NUM). Verbs Verbs are words that describe events and actions, e.g., fall and eat, as shown in Table 5-3. In the context of a sentence, verbs typically express a relation involving the referents of one or more noun phrases.
Ubiquitous Ambiguity A well-known example of ambiguity is shown in (2), from the Groucho Marx movie, Animal Crackers (1930): (2) While hunting in Africa, I shot an elephant in my pajamas. How an elephant got into my pajamas I’ll never know. Let’s take a closer look at the ambiguity in the phrase: I shot an elephant in my pajamas. First we need to define a simple grammar: >>> ... ... ... ... ... ... ... ... ... groucho_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) 8.1 Some Grammatical Dilemmas | 293 This grammar permits the sentence to be analyzed in two ways, depending on whether the prepositional phrase in my pajamas describes the elephant or the shooting event. >>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas'] >>> parser = nltk.ChartParser(groucho_grammar) >>> trees = parser.nbest_parse(sent) >>> for tree in trees: ... print tree (S (NP I) (VP (V shot) (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas)))))) (S (NP I) (VP (VP (V shot) (NP (Det an) (N elephant))) (PP (P in) (NP (Det my) (N pajamas))))) The program produces two bracketed structures, which we can depict as trees, as shown in (3): (3) a.
By convention, the lefthand side of the first production is the start-symbol of the grammar, typically S, and all well-formed trees must have this symbol as their root label. In NLTK, contextfree grammars are defined in the nltk.grammar module. In Example 8-1 we define a grammar and show how to parse a simple sentence admitted by the grammar. Example 8-1. A simple context-free grammar. grammar1 = nltk.parse_cfg(""" S -> NP VP VP -> V NP | V NP PP PP -> P NP V -> "saw" | "ate" | "walked" NP -> "John" | "Mary" | "Bob" | Det N | Det N PP Det -> "a" | "an" | "the" | "my" N -> "man" | "dog" | "cat" | "telescope" | "park" P -> "in" | "on" | "by" | "with" """) >>> sent = "Mary saw Bob".split() >>> rd_parser = nltk.RecursiveDescentParser(grammar1) >>> for tree in rd_parser.nbest_parse(sent): ... print tree (S (NP Mary) (VP (V saw) (NP Bob))) The grammar in Example 8-1 contains productions involving various syntactic categories, as laid out in Table 8-1.
Too Big to Know: Rethinking Knowledge Now That the Facts Aren't the Facts, Experts Are Everywhere, and the Smartest Person in the Room Is the Room by David Weinberger
airport security, Alfred Russel Wallace, Amazon Mechanical Turk, Berlin Wall, Black Swan, book scanning, Cass Sunstein, commoditize, corporate social responsibility, crowdsourcing, Danny Hillis, David Brooks, Debian, double entry bookkeeping, double helix, en.wikipedia.org, Exxon Valdez, Fall of the Berlin Wall, future of journalism, Galaxy Zoo, Hacker Ethic, Haight Ashbury, hive mind, Howard Rheingold, invention of the telegraph, jimmy wales, Johannes Kepler, John Harrison: Longitude, Kevin Kelly, linked data, Netflix Prize, New Journalism, Nicholas Carr, Norbert Wiener, openstreetmap, P = NP, Pluto: dwarf planet, profit motive, Ralph Waldo Emerson, RAND corporation, Ray Kurzweil, Republic of Letters, RFID, Richard Feynman, Ronald Reagan, semantic web, slashdot, social graph, Steven Pinker, Stewart Brand, technological singularity, Ted Nelson, the scientific method, The Wisdom of Crowds, Thomas Kuhn: the structure of scientific revolutions, Thomas Malthus, Whole Earth Catalog, X Prize
We’re just beginning to understand how.”33 That insight, and its development, occurred within a network of amateurs; had it been only a single person’s observation, the importance of “green peas” would not have been noticed. Indeed, the space within which credentialed science occurs is becoming dramatically and usefully more entwined with the rest of its environment. For example, on August 6, 2010, the mathematician Vinay Deolalikar sent to his colleagues a manuscript proposing a solution to a mathematical problem so notoriously difficult that there’s a million-dollar prize for solving it.34 The “P≠NP” problem had previously brought down some seriously brilliant mathematicians who thought they had it licked. This time, however, the person who originally formulated the problem emailed Deolalikar’s solution to some of his colleagues, saying, “This appears to be a relatively serious claim to have solved P vs. NP.” This highly authoritative endorsement made the paper go viral, at least within the limited world of mathematicians interested in such matters.
Elliptic Tales: Curves, Counting, and Number Theory by Avner Ash, Robert Gross
The set E(Fp )ns is still nonempty, and is in fact also an abelian group, just as E(Fp ) was for good p, as we saw in chapter 9. We let Np stand for the number of points in E(Fp )ns . For the good primes p, E modulo p is nonsingular, so Np is simply the number of points in E(Fp ). For the bad primes p, we worked out Np in chapter 9. The results, taken from table 9.4, are that Np = p if E has additive reduction at p, Np = p − 1 if E has split multiplicative reduction at p, and Np = p + 1 if E has nonsplit multiplicative reduction at p. Next we review the definition of the integer ap , defined for every prime p . If E modulo p is nonsingular (good p), we set Np = p + 1 − ap . 208 CHAPTER 13 If E modulo p is singular (bad p), we set Np = p − ap , where we took away 1 because E(Fp ) has one singular point that we are not counting.
The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World by Pedro Domingos
Albert Einstein, Amazon Mechanical Turk, Arthur Eddington, basic income, Bayesian statistics, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, creative destruction, crowdsourcing, Danny Hillis, data is the new oil, double helix, Douglas Hofstadter, Erik Brynjolfsson, experimental subject, Filter Bubble, future of work, global village, Google Glasses, Gödel, Escher, Bach, information retrieval, job automation, John Markoff, John Snow's cholera map, John von Neumann, Joseph Schumpeter, Kevin Kelly, lone genius, mandelbrot fractal, Mark Zuckerberg, Moneyball by Michael Lewis explains big data, Narrative Science, Nate Silver, natural language processing, Netflix Prize, Network effects, NP-complete, off grid, P = NP, PageRank, pattern recognition, phenotype, planetary scale, pre–internet, random walk, Ray Kurzweil, recommendation engine, Richard Feynman, scientific worldview, Second Machine Age, self-driving car, Silicon Valley, social intelligence, speech recognition, Stanford marshmallow experiment, statistical model, Stephen Hawking, Steven Levy, Steven Pinker, superintelligent machines, the scientific method, The Signal and the Noise by Nate Silver, theory of mind, Thomas Bayes, transaction costs, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, white flight, zero-sum game
Average Is Over: Powering America Beyond the Age of the Great Stagnation by Tyler Cowen
Amazon Mechanical Turk, Black Swan, brain emulation, Brownian motion, business cycle, Cass Sunstein, choice architecture, complexity theory, computer age, computer vision, computerized trading, cosmological constant, crowdsourcing, dark matter, David Brooks, David Ricardo: comparative advantage, deliberate practice, Drosophila, en.wikipedia.org, endowment effect, epigenetics, Erik Brynjolfsson, eurozone crisis, experimental economics, Flynn Effect, Freestyle chess, full employment, future of work, game design, income inequality, industrial robot, informal economy, Isaac Newton, Johannes Kepler, John Markoff, Khan Academy, labor-force participation, Loebner Prize, low skilled workers, manufacturing employment, Mark Zuckerberg, meta analysis, meta-analysis, microcredit, Myron Scholes, Narrative Science, Netflix Prize, Nicholas Carr, P = NP, pattern recognition, Peter Thiel, randomized controlled trial, Ray Kurzweil, reshoring, Richard Florida, Richard Thaler, Ronald Reagan, Silicon Valley, Skype, statistical model, stem cell, Steve Jobs, Turing test, Tyler Cowen: Great Stagnation, upwardly mobile, Yogi Berra
Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier
active measures, cellular automata, Claude Shannon: information theory, complexity theory, dark matter, Donald Davies, Donald Knuth, dumpster diving, Exxon Valdez, fault tolerance, finite state, invisible hand, John von Neumann, knapsack problem, MITM: man-in-the-middle, NP-complete, P = NP, packet switching, RAND corporation, RFC: Request For Comment, software patent, telemarketer, traveling salesman, Turing machine, web of trust, Zimmermann PGP
Bennett and G. Brassard, “Quantum Public Key Distribution Reinvented,” SIGACT News, v. 18, n. 4, 1987, pp. 51–53. 127. C.H. Bennett and G. Brassard, “The Dawn of a New Era for Quantum Cryptography: The Experimental Prototype is Working!” SIGACT News, v. 20, n. 4, Fall 1989, pp. 78–82. 128. C.H. Bennett, G. Brassard, and S. Breidbart, Quantum Cryptography II: How to Re–Use a One–Time Pad Safely Even if P=NP, unpublished manuscript, Nov 1982. 129. C.H. Bennett, G. Brassard, S. Breidbart, and S. Weisner, “Quantum Cryptography, or Unforgeable Subway Tokens,” Advances in Cryptology: Proceedings of Crypto 82, Plenum Press, 1983, pp. 267–275. 130. C.H. Bennett, G. Brassard, C. Crépeau, and M.–H. Skubiszewska, “Practical Quantum Oblivious Transfer,” Advances in Cryptology—CRYPTO ’91 Proceedings, Springer–Verlag, 1992, pp. 351–366. 131.
The End of Money: Counterfeiters, Preachers, Techies, Dreamers--And the Coming Cashless Society by David Wolman
addicted to oil, Bay Area Rapid Transit, Berlin Wall, Bernie Madoff, bitcoin, Bretton Woods, carbon footprint, cashless society, central bank independence, collateralized debt obligation, corporate social responsibility, credit crunch, cross-subsidies, Diane Coyle, fiat currency, financial innovation, floating exchange rates, German hyperinflation, greed is good, Isaac Newton, Kickstarter, M-Pesa, Mahatma Gandhi, mental accounting, mobile money, money: store of value / unit of account / medium of exchange, offshore financial centre, P = NP, Peter Thiel, place-making, placebo effect, Ponzi scheme, Ronald Reagan, seigniorage, Silicon Valley, special drawing rights, Steven Levy, the payments system, transaction costs, WikiLeaks
Hands-On Machine Learning With Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems by Aurelien Geron
Amazon Mechanical Turk, Bayesian statistics, centre right, combinatorial explosion, constrained optimization, correlation coefficient, crowdsourcing, en.wikipedia.org, iterative process, Netflix Prize, NP-complete, optical character recognition, P = NP, p-value, pattern recognition, performance metric, recommendation engine, self-driving car, SpamAssassin, speech recognition, statistical model
The Music of the Primes by Marcus Du Sautoy
Ada Lovelace, Andrew Wiles, Arthur Eddington, Augustin-Louis Cauchy, computer age, Dava Sobel, Dmitri Mendeleev, Eratosthenes, Erdős number, Georg Cantor, German hyperinflation, global village, Henri Poincaré, Isaac Newton, Jacquard loom, lateral thinking, music of the spheres, New Journalism, P = NP, Paul Erdős, Richard Feynman, Rubik’s Cube, Search for Extraterrestrial Intelligence, Simon Singh, Solar eclipse in 1919, Stephen Hawking, Turing machine, William of Occam, Wolfskehl Prize, Y2K
Asset and Risk Management: Risk Oriented Finance by Louis Esch, Robert Kieffer, Thierry Lopez
asset allocation, Brownian motion, business continuity plan, business process, capital asset pricing model, computer age, corporate governance, discrete time, diversified portfolio, fixed income, implied volatility, index fund, interest rate derivative, iterative process, P = NP, p-value, random walk, risk/return, shareholder value, statistical model, stochastic process, transaction costs, value at risk, Wiener process, yield curve, zero-coupon bond
How I Became a Quant: Insights From 25 of Wall Street's Elite by Richard R. Lindsey, Barry Schachter
Albert Einstein, algorithmic trading, Andrew Wiles, Antoine Gombaud: Chevalier de Méré, asset allocation, asset-backed security, backtesting, bank run, banking crisis, Black-Scholes formula, Bonfire of the Vanities, Bretton Woods, Brownian motion, business cycle, business process, butter production in bangladesh, buy and hold, buy low sell high, capital asset pricing model, centre right, collateralized debt obligation, commoditize, computerized markets, corporate governance, correlation coefficient, creative destruction, Credit Default Swap, credit default swaps / collateralized debt obligations, currency manipulation / currency intervention, discounted cash flows, disintermediation, diversification, Donald Knuth, Edward Thorp, Emanuel Derman, en.wikipedia.org, Eugene Fama: efficient market hypothesis, financial innovation, fixed income, full employment, George Akerlof, Gordon Gekko, hiring and firing, implied volatility, index fund, interest rate derivative, interest rate swap, John von Neumann, linear programming, Loma Prieta earthquake, Long Term Capital Management, margin call, market friction, market microstructure, martingale, merger arbitrage, Myron Scholes, Nick Leeson, P = NP, pattern recognition, Paul Samuelson, pensions crisis, performance metric, prediction markets, profit maximization, purchasing power parity, quantitative trading / quantitative ﬁnance, QWERTY keyboard, RAND corporation, random walk, Ray Kurzweil, Richard Feynman, Richard Stallman, risk-adjusted returns, risk/return, shareholder value, Sharpe ratio, short selling, Silicon Valley, six sigma, sorting algorithm, statistical arbitrage, statistical model, stem cell, Steven Levy, stochastic process, systematic trading, technology bubble, The Great Moderation, the scientific method, too big to fail, trade route, transaction costs, transfer pricing, value at risk, volatility smile, Wiener process, yield curve, young professional
Hands-On Machine Learning With Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems by Aurélien Géron
Amazon Mechanical Turk, Anton Chekhov, combinatorial explosion, computer vision, constrained optimization, correlation coefficient, crowdsourcing, don't repeat yourself, Elon Musk, en.wikipedia.org, friendly AI, ImageNet competition, information retrieval, iterative process, John von Neumann, Kickstarter, natural language processing, Netflix Prize, NP-complete, optical character recognition, P = NP, p-value, pattern recognition, pull request, recommendation engine, self-driving car, sentiment analysis, SpamAssassin, speech recognition, stochastic process
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook
complexity theory, computer age, Computer Numeric Control, four colour theorem, index card, John von Neumann, linear programming, NP-complete, P = NP, p-value, RAND corporation, Richard Feynman, traveling salesman, Turing machine
In Pursuit of Privilege: A History of New York City's Upper Class and the Making of a Metropolis by Clifton Hood
affirmative action, British Empire, coherent worldview, David Brooks, death of newspapers, deindustrialization, family office, Golden Gate Park, Google Earth, jitney, mass immigration, new economy, New Urbanism, P = NP, plutocrats, Plutocrats, Ray Oldenburg, ride hailing / ride sharing, Scientific racism, selection bias, Steven Levy, The Great Good Place, Thorstein Veblen, trade route, urban planning, We are the 99%, white flight
Python for Finance by Yuxing Yan
asset-backed security, business cycle, business intelligence, capital asset pricing model, constrained optimization, correlation coefficient, distributed generation, diversified portfolio, implied volatility, market microstructure, P = NP, p-value, quantitative trading / quantitative ﬁnance, Sharpe ratio, time value of money, value at risk, volatility smile, zero-sum game
In the following program, we have three input values: ticker, begdate (first date), and enddate (second date): import datetime import matplotlib.pyplot as plt from matplotlib.finance import quotes_historical_yahoo from matplotlib.dates import MonthLocator,DateFormatter ticker='AAPL' begdate= datetime.date( 2012, 1, 2 ) enddate = datetime.date( 2013, 12,4) months = MonthLocator(range(1,13), bymonthday=1, interval=3) # every 3rd month monthsFmt = DateFormatter("%b '%Y") x = quotes_historical_yahoo(ticker, begdate, enddate) if len(x) == 0: print ('Found no quotes') raise SystemExit dates = [q for q in x] closes = [q for q in x] fig, ax = plt.subplots() ax.plot_date(dates, closes, '-') ax.xaxis.set_major_locator(months) ax.xaxis.set_major_formatter(monthsFmt) ax.xaxis.set_minor_locator(mondays) ax.autoscale_view() ax.grid(True) fig.autofmt_xdate() [ 153 ] Visual Finance via Matplotlib The output graph is shown as follows: IBM's intra-day graphical representations We could demonstrate the price movement of a stock for a given period, for example, from January 2009 to today. First, let's look at the intra-day price pattern. The following program will be explained in the next chapter: import pandas as pd, numpy as np, datetime ticker='AAPL' path='http://www.google.com/finance/getprices?q=ttt&i=60&p=1d&f=d,o,h,l,c ,v' p=np.array(pd.read_csv(path.replace('ttt',ticker),skiprows=7,header=No ne)) date= for i in arange(0,len(p)): if p[i]=='a': t= datetime.datetime.fromtimestamp(int(p[i].replace('a',''))) date.append(t) else: date.append(t+datetime.timedelta(minutes =int(p[i]))) [ 154 ] Chapter 7 final=pd.DataFrame(p,index=date) final.columns=['a','Open','High','Low','Close','Vol'] del final['a'] x=final.index y=final.Close title('Intraday price pattern for ttt'.replace('ttt',ticker)) xlabel('Price of stock') ylabel('Intro-day price pattern') plot(x,y) show() The graph is shown in the following image: [ 155 ] Visual Finance via Matplotlib A more complex program that we can run to find the intra-day pattern could be found at http://matplotlib.org/examples/pylab_examples/finance_work2. html.
Only affects DataFrame / 2d ndarray input Return estimation If we have price data, we have to calculate returns. In addition, sometimes we have to convert daily returns to weekly or monthly, or convert monthly returns to quarterly or annual. Thus, understanding how to estimate returns and their conversion is vital. Assume that we have four prices and we choose the first and last three prices as follows: >>>import numpy as np >>>p=np.array([1,1.1,0.9,1.05]) [ 185 ] Statistical Analysis of Time Series It is important how these prices are sorted. If the first price happened before the second price, we know that the first return should be (1.1-1)/1=10%. Next, we learn how to retrieve the first n-1 and the last n-1 records from an n-record array. To list the first n-1 prices, we use p[:-1], while for the last three prices we use p[1:] as shown in the following code: >>>print(p[:-1]) >>>print(p[1:]) [ 1. 1.1 [ 1.1 0.9 0.9] 1.05] To estimate returns, use the following code: >>>ret=(p[1:]-p[:-1])/p[:-1] >>>print ret [ 0.1 -0.18181818 0.16666667] However, if the prices are arranged in the reverse order, for example, the first one is the latest price and the last one is the oldest price, then we have to estimate returns in the following ways: >>>ret=(p[:-1]-p[1:])/p[1:] >>>print ret [-0.09090909 0.22222222 -0.14285714] >>> The following code shows how to download daily price data from Yahoo!
If we estimate the illiquidity for DELL over the same period, we would find a value of 0.638*10-11. Since 1.165 is greater than 0.638, we conclude that IBM is less liquid than DELL. This correlation is represented in the following code: import numpy as np import statsmodels.api as sm from matplotlib.finance import quotes_historical_yahoo begdate=(2013,10,1) enddate=(2013,10,30) ticker='IBM' #WMT data= quotes_historical_yahoo(ticker, begdate, enddate,asobject=True, adjusted=True) p=np.array(data.aclose) dollar_vol=np.array(data.volume*p) ret=np.array((p[1:] - p[:-1])/p[1:]) illiq=mean(np.divide(abs(ret),dollar_vol[1:])) print("Aminud illiq=", illiq) ('Aminud illiq=', 1.1650681670001537e-11) Pastor and Stambaugh (2003) liquidity measure Based on the methodology and empirical evidence in Campbell, Grossman, and Wang (1993), Pastor and Stambaugh (2003) designed the following model to measure individual stock's liquidity and the market liquidity: \W D E [W E [W W (9) Here, yt is the excess stock return, 5W 5 I W , on day t, 5W is the return for the stock, 5 I W is the risk-free rate, [W is the market return; [W is the signed dollar trading volume ( x2,t = sign Rt − R f ,t ∗ pt ∗ volumet), pt is the stock price, and YROXPHW is the trading volume.
Reinventing Discovery: The New Era of Networked Science by Michael Nielsen
Albert Einstein, augmented reality, barriers to entry, bioinformatics, Cass Sunstein, Climategate, Climatic Research Unit, conceptual framework, dark matter, discovery of DNA, Donald Knuth, double helix, Douglas Engelbart, Douglas Engelbart, en.wikipedia.org, Erik Brynjolfsson, fault tolerance, Fellow of the Royal Society, Firefox, Freestyle chess, Galaxy Zoo, Internet Archive, invisible hand, Jane Jacobs, Jaron Lanier, Johannes Kepler, Kevin Kelly, Magellanic Cloud, means of production, medical residency, Nicholas Carr, P = NP, publish or perish, Richard Feynman, Richard Stallman, selection bias, semantic web, Silicon Valley, Silicon Valley startup, Simon Singh, Skype, slashdot, social intelligence, social web, statistical model, Stephen Hawking, Stewart Brand, Ted Nelson, The Death and Life of Great American Cities, The Nature of the Firm, The Wisdom of Crowds, University of East Anglia, Vannevar Bush, Vernor Vinge
Advances in Financial Machine Learning by Marcos Lopez de Prado
algorithmic trading, Amazon Web Services, asset allocation, backtesting, bioinformatics, Brownian motion, business process, Claude Shannon: information theory, cloud computing, complexity theory, correlation coefficient, correlation does not imply causation, diversification, diversified portfolio, en.wikipedia.org, fixed income, Flash crash, G4S, implied volatility, information asymmetry, latency arbitrage, margin call, market fragmentation, market microstructure, martingale, NP-complete, P = NP, p-value, paper trading, pattern recognition, performance metric, profit maximization, quantitative trading / quantitative ﬁnance, RAND corporation, random walk, risk-adjusted returns, risk/return, selection bias, Sharpe ratio, short selling, Silicon Valley, smart cities, smart meter, statistical arbitrage, statistical model, stochastic process, survivorship bias, transaction costs, traveling salesman
Human Compatible: Artificial Intelligence and the Problem of Control by Stuart Russell
3D printing, Ada Lovelace, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Alfred Russel Wallace, Andrew Wiles, artificial general intelligence, Asilomar, Asilomar Conference on Recombinant DNA, augmented reality, autonomous vehicles, basic income, blockchain, brain emulation, Cass Sunstein, Claude Shannon: information theory, complexity theory, computer vision, connected car, crowdsourcing, Daniel Kahneman / Amos Tversky, delayed gratification, Elon Musk, en.wikipedia.org, Erik Brynjolfsson, Ernest Rutherford, Flash crash, full employment, future of work, Gerolamo Cardano, ImageNet competition, Intergovernmental Panel on Climate Change (IPCC), Internet of things, invention of the wheel, job automation, John Maynard Keynes: Economic Possibilities for our Grandchildren, John Maynard Keynes: technological unemployment, John Nash: game theory, John von Neumann, Kenneth Arrow, Kevin Kelly, Law of Accelerating Returns, Mark Zuckerberg, Nash equilibrium, Norbert Wiener, NP-complete, openstreetmap, P = NP, Pareto efficiency, Paul Samuelson, Pierre-Simon Laplace, positional goods, probability theory / Blaise Pascal / Pierre de Fermat, profit maximization, RAND corporation, random walk, Ray Kurzweil, recommendation engine, RFID, Richard Thaler, ride hailing / ride sharing, Robert Shiller, Robert Shiller, Rodney Brooks, Second Machine Age, self-driving car, Shoshana Zuboff, Silicon Valley, smart cities, smart contracts, social intelligence, speech recognition, Stephen Hawking, Steven Pinker, superintelligent machines, Thales of Miletus, The Future of Employment, Thomas Bayes, Thorstein Veblen, transport as a service, Turing machine, Turing test, universal basic income, uranium enrichment, Von Neumann architecture, Wall-E, Watson beat the top human players on Jeopardy!, web application, zero-sum game
The Wrecking Crew: How Conservatives Rule by Thomas Frank
affirmative action, anti-communist, barriers to entry, Berlin Wall, Bernie Madoff, British Empire, business cycle, collective bargaining, corporate governance, Credit Default Swap, David Brooks, edge city, financial deregulation, full employment, George Gilder, guest worker program, income inequality, invisible hand, job satisfaction, Mikhail Gorbachev, Mont Pelerin Society, mortgage debt, Naomi Klein, Nelson Mandela, new economy, P = NP, plutocrats, Plutocrats, Ponzi scheme, Ralph Nader, rent control, Richard Florida, road to serfdom, rolodex, Ronald Reagan, school vouchers, shareholder value, Silicon Valley, stem cell, Telecommunications Act of 1996, the scientific method, too big to fail, union organizing, War on Poverty
Phillips reprinted the memo as appendix B in his book The New Right at Harvard (Vienna, Va.: Conservative Caucus, 1983), p. 181. 27. The word “revolution” could even take on the wistful notes of lost youth, as at a 1992 College Republican reunion when Abramoff, by then a producer of wretched movies, hosted an alumni session called “Rejoin the Revolution.” See 1992 College Republicans’ Centennial Celebration (n.p.: n.p., n.d. ). Sword and shield: “Message from the Chairman” in the 1983 Annual Report of the College Republicans, p. 3. The phrase is also used in the 1982 Review of the NEWS interview cited above and in a 1995 profile by John W. Moore, “A Lobbyist With a Line to Capitol Hill,” National Journal, July 29, 1995. “Fighting for the Revolution”: CR Report, May 14, 1983, p. 5. 1984 Republican Convention: Raleigh E.
Waller also thanks Abramoff in the acknowledgments of his 1991 book, The Third Current of Revolution. Since the breaking of the Abramoff scandal, however, Waller has become a frequent critic of the fallen lobbyist, recounting for other journalists how Abramoff played Washington’s right-wing network for his various lobbying clients. (He did not respond to inquiries from me.) “Deputy projects director”: College Republican National Committee, Forty-Fifth Biennial Convention (n.p.: n.p., 1983), n.p. YAF magazine: J. Michael Waller, “Bare-Fisted Journalism,” New Guard, Winter 1982–83, p. 37. Crashing the IPS party: CR Report, May 14, 1983, p. 2. USA Foundation: J. Michael Waller, “CISPES: A Guerrilla Propaganda Network,” a twenty-one-page report printed on United Students of America Foundation letterhead, with a cover letter signed by Jack Abramoff and dated November 7, 1983, from collections of Political Research Associates.
“CNMI policy permits the staffing of major employers in the territory—garment factories, security companies, the hotel industry—with a permanent floating army of foreign workers who have no opportunity to become permanent members of the community and who, by nature of their status, culture and powerlessness, are extremely vulnerable to exploitation, pressure, and mistreatment.” Congressman George Miller and Democratic Staff of the House Committee on Resources, “Beneath the American Flag: Labor and Human Rights Abuses in the CNMI” (n.p.: n.p., March 26, 1998), p. 15. 9. “The fact that an employer can have an alien worker removed from the CNMI on one-day’s notice is a powerful incentive for an alien to obey an employer’s demands, even though the demands may be illegal or abusive.” Third Annual Report, p. 11. 10. As of 1997, the minimum wage in Saipan for garment and construction workers was $2.90 per hour; for more exalted occupations it was $3.05 per hour.
The Art of Computer Programming by Donald Ervin Knuth
Brownian motion, complexity theory, correlation coefficient, Donald Knuth, Eratosthenes, G4S, Georg Cantor, information retrieval, Isaac Newton, iterative process, John von Neumann, Louis Pasteur, mandelbrot fractal, Menlo Park, NP-complete, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, RAND corporation, random walk, sorting algorithm, Turing machine, Y2K
Global Catastrophic Risks by Nick Bostrom, Milan M. Cirkovic
affirmative action, agricultural Revolution, Albert Einstein, American Society of Civil Engineers: Report Card, anthropic principle, artificial general intelligence, Asilomar, availability heuristic, Bill Joy: nanobots, Black Swan, carbon-based life, cognitive bias, complexity theory, computer age, coronavirus, corporate governance, cosmic microwave background, cosmological constant, cosmological principle, cuban missile crisis, dark matter, death of newspapers, demographic transition, Deng Xiaoping, distributed generation, Doomsday Clock, Drosophila, endogenous growth, Ernest Rutherford, failed state, feminist movement, framing effect, friendly AI, Georg Cantor, global pandemic, global village, Gödel, Escher, Bach, hindsight bias, Intergovernmental Panel on Climate Change (IPCC), invention of agriculture, Kevin Kelly, Kuiper Belt, Law of Accelerating Returns, life extension, means of production, meta analysis, meta-analysis, Mikhail Gorbachev, millennium bug, mutually assured destruction, nuclear winter, P = NP, peak oil, phenotype, planetary scale, Ponzi scheme, prediction markets, RAND corporation, Ray Kurzweil, reversible computing, Richard Feynman, Ronald Reagan, scientific worldview, Singularitarianism, social intelligence, South China Sea, strong AI, superintelligent machines, supervolcano, technological singularity, technoutopianism, The Coming Technological Singularity, Tunguska event, twin studies, uranium enrichment, Vernor Vinge, War on Poverty, Westphalian system, Y2K
Rationality: From AI to Zombies by Eliezer Yudkowsky
Albert Einstein, Alfred Russel Wallace, anthropic principle, anti-pattern, anti-work, Arthur Eddington, artificial general intelligence, availability heuristic, Bayesian statistics, Berlin Wall, Build a better mousetrap, Cass Sunstein, cellular automata, cognitive bias, cognitive dissonance, correlation does not imply causation, cosmological constant, creative destruction, Daniel Kahneman / Amos Tversky, dematerialisation, different worldview, discovery of DNA, Douglas Hofstadter, Drosophila, effective altruism, experimental subject, Extropian, friendly AI, fundamental attribution error, Gödel, Escher, Bach, hindsight bias, index card, index fund, Isaac Newton, John Conway, John von Neumann, Long Term Capital Management, Louis Pasteur, mental accounting, meta analysis, meta-analysis, money market fund, Nash equilibrium, Necker cube, NP-complete, P = NP, pattern recognition, Paul Graham, Peter Thiel, Pierre-Simon Laplace, placebo effect, planetary scale, prediction markets, random walk, Ray Kurzweil, reversible computing, Richard Feynman, risk tolerance, Rubik’s Cube, Saturday Night Live, Schrödinger's Cat, scientific mainstream, scientific worldview, sensible shoes, Silicon Valley, Silicon Valley startup, Singularitarianism, Solar eclipse in 1919, speech recognition, statistical model, Steven Pinker, strong AI, technological singularity, The Bell Curve by Richard Herrnstein and Charles Murray, the map is not the territory, the scientific method, Turing complete, Turing machine, ultimatum game, X Prize, Y Combinator, zero-sum game