More on this book
Community
Kindle Notes & Highlights
problems where the rules aren’t clear, some of the required information is missing, or finding exactly the right answer would require considering an astronomical number of possibilities—that now pose the biggest challenges in computer science.
cri de coeur,
In any system responsible for managing a vast data base there must be failures of retrieval.
It is just too expensive to maintain access to an unbounded
number of ...
This highlight has been truncated due to consecutive passage length restrictions.
what we call “cognitive decline”—lags and retrieval errors—may not be about the search process slowing or deteriorating, but (at least partly) an unavoidable consequence of the amount of information we have to navigate getting bigger and bigger.
status of about 7% of all problems is still unknown,
only 9% can be solved efficiently, and the other 84% have been proven intractable.
Intriguingly, optimizing all these other metrics is intractable if we know the start times and durations of jobs ahead of time.
Even with complete foreknowledge, finding the perfect schedule might be practically impossible.
the machine that is doing the scheduling and the machine being scheduled are one and the same.
Every time you switch tasks, you pay a price, known in computer science as a context switch.
The moral is that you should try to stay on a single task as long as possible without decreasing your responsiveness below the minimum acceptable limit.
the process of “preferential attachment” is one of the surest ways to produce a power-law distribution.
The reason we can often make good predictions from a small number of observations—or just a single one—is that our priors are so rich.
Walter Mischel ran his famous “marshmallow test”
He is careful of what he reads, for that is what he will write. He is careful of what he learns, for that is what he will know.
“Incentive structures work,” as Steve Jobs put it. “So you have to be very careful of what you incent people to do, because various incentive structures create all sorts of consequences that you can’t anticipate.”
Andrey Tikhonov
If we introduce a complexity penalty, then more complex models need to do not merely a better job but a significantly better job of explaining the data to justify their greater complexity.
One algorithm, discovered in 1996 by biostatistician Robert Tibshirani, is called the Lasso
“artificial neural networks,” can learn arbitrarily complex functions—they’re even more flexible than our nine-factor model above—but precisely because of this very flexibility they are notoriously vulnerable to overfitting.
Neuroscientists have suggested, for instance, that brains try to minimize the number of neurons that are firing at any given moment—implementing the same kind of downward pressure on complexity as the Lasso.
Constraint Relaxation, simply removes some constraints altogether and makes progress on a looser form of the problem before coming back to reality.
Continuous Relaxation, turns discrete or binary choices into continua:
Lagrangian Relaxation, turns impossibilities into mere penalties, teaching the art of bending the rules
they offer a bound on the quality of the true solution.
relaxations are designed so that they can indeed be reconciled with reality—and
F. Scott Fitzgerald once wrote that “the test of a first-rate intelligence is the ability to hold two opposing ideas in mind at the same time and still retain the ability to function.”
Sieve of Erastothenes.
“one-way function.”
Miller-Rabin primality test,
the word is rooted in the Greek protokollon, “first glue,” which referred to the outer page attached to a book or manuscript.
packet switching.
ability to operate agnostically over any number of diverse media would be packet switching’s great virtue.
acknowledgment packets, or ACKs.
At the heart of TCP congestion control is an algorithm called Additive Increase, Multiplicative Decrease, or AIMD.
buffers use delay—known in networking as “latency”—in order to maximize throughput.
“If an equilibrium concept is not efficiently computable, much of its credibility as a prediction of the behavior of rational agents is lost.”
A dominant strategy avoids recursion altogether, by being the best response to all of your opponent’s possible strategies—so
Whenever you find yourself on the side of the majority, it is time to pause and reflect.
“sealed-bid first-price auction,”
“Dutch auction” or “descending auction,” gradually lowers an item’s price until someone is willing to buy it.
English auction, bidders alternate raising the price until all but one of them drop out.
a group of agents who are all behaving perfectly rationally and perfectly appropriately can nonetheless fall prey to what is effectively infinite misinformation.
“information cascade.”
Vickrey auction,
“revelation principle,” Nobel laureate Roger Myerson proved that any game that requires strategically masking the truth can be transformed into a game that requires nothing
Nisan puts it, “The basic thing is if you don’t want your clients to optimize against you, you’d better optimize for them.
