Monday, November 29, 2010

Complexity as Friction

What advantages can we get from computational hardness? Cryptography and pseudo-random number generators come to mind. But perhaps the universe made computation difficult for a reason, not unlike friction.

In the physical world friction usually costs us energy to overcome but on the other hand we can't walk without it. In the computational world, complexity can often slow progress but if it didn't exist we could have many other problems.

We've seen a taste of this as computers got faster, information more accessible and better algorithmic tools particularly in learning and search.
  • Privacy: We can now store more information about each person and even the old information is much easier to access. Perhaps as important we can now learn more from less with much better algorithms. We're almost at the point where computers know more about us than we know about ourselves.
  • Markets: Two words: Flash Crash 
  • Airlines: We can easily find the cheapest airline flights and so airlines have put considerable effort into competing on this single dimension of price at the expense of the whole flying experience. This has also reduced competition where now airlines have cut capacity so they can keep prices higher.
  • Politics: Politicians act as a proxy for the people in a democracy and we entrusted them to make difficult decisions because we didn't have the tools to help in these processes ourselves. But now we have much more access giving less flexibility to politicians, making them focus more on the short term instead of the longer picture and polarizing our politics.
This is just a few of many such stories. As computer scientists our goal is to make computation as efficient and simple as possible but we must keep in our minds the costs of reducing the friction too much.


  1. Really good examples, except I don't follow how in politics efficiency increases polarization.

  2. (1) In these examples it seems you are talking more about storage capacity and network speed rather than computational complexity per se.

    (2) I find your last example particularly interesting in light of the latest wiki-leaks release. How are governments going to be able to conduct honest internal discussions if they know any "true but undiplomatic" opinions are liable to be leaked with just a click? They would either have to limit their candor or avoid electronic communications all together neither of which is a particularly good idea.

    Also your point about transparency polarizing politics is a good one, in many ways it gets back to the idea of whether things would run better if the "experts" were left to decide things without facing too much populist pressure from the "mob" - This is sort of Plato's idea of "Philosopher Kings."

    Of course that idea is also very problematic - elites can get corrupt and complacent.

    Also makes me think of David Brin's idea of "The Transparent Society" - are we really ready for a reality in which privacy becomes extremely limited?

  3. This seems to me to be a deeply provocative concept, to the degree that it challenges an awful lot of our preconceptions about where 'cheap information' is taking us - possibly to a world as dysfunctional as the one that 'cheap energy' has brought about.

  4. Anon #2: Citizens have been living with lack of privacy for a long time. Now governments are too. What goes around come around.

  5. @Geoff

    Suppose a panel of bi-partisan experts issues a report that the best way to eliminate the deficit is to BOTH increase some taxes AND cut some spending on Social Security/Medicare.

    Now due to blogs, the very INSTANT there is even a rumor that Republicans are considering this proposal a sensationalist headline will appear on Politico: "Republicans To Increase Taxes. Utterly Betraying Their Base!!!" Grover Norquist and the Club for Growth will issue a blistering statement. 1000s of emails will deluge the Capitol. The Republicans will be forced to issue a statement: "We will not support ANY tax increases. Over our dead bodies!"

    The same idea applies to Democrats and cutting spending on Medicare/Social Security of course.

    In the past there would have been less immediate political pressure and more time for quiet negotiations and perhaps eventually a deal would have been struck that enjoyed fairly broad public support.

    I think this is what Lance is referring to.

  6. This is a great post! Dynamicists have long known that simulations and predictions (both classical and quantum) that are intractable in the absence of friction and noise become tractable when friction and noise are present.

    Classical example: The Hamiltonian flow associated to Euler dynamics is (thought to be) computationally intractable; the viscous flow associated to Navier-Stokes dynamics is (thought to be) computationally tractable.

    Quantum example: The Hamiltonian flow associated to Schroedinger dynamics is (thought to be) computationally intractable; the compresive flow associated to the Lindbladian dynamics is (thought to be) computationally tractable.

    I have often wondered whether our universe's ubiquitous black-body radiation, space-time curvature, and black-hole singularities are Nature's way of ensuring that computing her own evolution is not computationally extravagant.

    Lance's insight that markets need friction is morally to-the-point also (IMHO) ... that moral point being, that efficient markets operating on microsecond time scales, such that participation by ordinary citizens is infeasible, are not "just" in any sense that the Founders would recognize.

  7. @Anonymous3: I see your point. It would be reasonable for REP/DEM to hold extreme positions just as bargaining ploys, since either extreme is untenable, if only either would budge, since neither represents a national consensus. In game theory, have economists modeled the bargaining that goes on in Asian street markets, with all the haggling? Can't it be demonstrated that a congress or market devoid of negotiation does not make progress? Or that rigidity leads to unsolvable complexity?

  8. For those that are interested. Here are a couple of fun articles of mine in this vein.

  9. Lance/Bill: Now that most job openings have been announced, it would be useful to have a post summarizing all of the openings that are targeting theorists. I know that the CCI site is supposed to do this, but it is failing. I know, for example, that Caltech, Johns Hopkins, and UPenn all have theory friendly job posts out, and are missing from CCI. Who knows what else I am missing?

    This blog is a great central meeting place for the community, so seems like a natural place to aggregate job listings in a single post.


    Anon job seeker

  10. Completely agree with #4. It is clear from opinion polls that we citizens don't trust our politicians at all, we all know how corrupt they are, elections are won by spending huge amounts of money, etc etc. Liberal vote for the fear of tea-party, conservatives vote for the fear of socialists, we vote not because we support a politician but for the fear of the other side.

    Governments have been promising citizens that they are going to be more transparent for centuries, now they are going to be forced to be transparent. They are going to be forced to do less evil and kill less people, topple less democratically elected governments, support less brutal authoritarian dictatorships, ... . This is the time for real change, not just promises, but change we can believe in.

    And for airlines, it is just an example of market system failure.

  11. "making them focus more on the short term"

    you say that as if it's a good thing when in reality it is one of the biggest problems

  12. I'm not sure I agree on the third point ("airlines"). To the contrary, one would think it would be easy to list, alongside the airfare, whether a meal is included and how much extra you would have to pay to check your bags (much as froogle does when it lists price as well as tax + shipping).

  13. Physicist Sean Carroll in "From Eternity to Here" has a related quote: "Life is organized friction"

    If we combine the two concepts we get...

  14. Very thought provoking post! It is not clear if the "friction" in the examples discussed in the post are caused by limited computational power or by a more basic issue of missing information.

  15. I agree with Gil ... often times the biggest challenge in information processing is not acquiring more information, or processing the information that one has, but rather culling information.

    Friction is (it seems to me) a generic term for the natural processes by which Nature culls information. There are many such processes: viscosity in fluid dynamics, noise in quantum dynamics, entropy increase in both classical and quantum thermodynamics, etc.

    The thesis that Nature's own dynamical resources suffice to simulate herself is one way to state what Scott Aaronson has taken to calling the Extended Church-Turing Thesis (ECT)

    Like most engineers, I am well-disposed toward the ECT, for the teleological reason that the universal phenomena of 4K black-body radiation, space-time curvature, and black hole singularities can be regarded as existing solely to enforce the ECT.

    The point is that the same ECT that makes the work of the Author of Nature exponentially easier, also makes the work of us human engineers exponentially easier. Good! :)

  16. Also, computational "friction" has been proposed as a way to protect elections from manipulation: