Friday, January 16, 2009

Planes. Fellows. Power.

It was a common joke to point out how people really overestimate low or zero probability events. Why in the pre-flight briefing do the flight attendants teach us not one but two ways to inflate our life vests when there has never been a successful emergency water landing of a commercial airplane? Never. Ever. Until yesterday.

Suresh posts about the new ACM Fellows. Congrats to all!

Kirk Pruhs asks us to plug the Workshop on the Science of Power Management.

In particular it would be interesting to see if some interesting complexity theory could be built for energy/power as a resource instead of the usual complexity of space/time. On one hand, it is not immediately obvious how to do this as energy seems quite different than space/time, e.g. I guess there is no energy hierarchy theorem analogous to the space/time hierarchy theorems. On the other hand, I would be surprised if there is just no interesting complexity theory of energy.
In the Clinton administration it helped to make research relevant to the Internet. In the Bush administration it helped to make research relevant to national security. In the Obama administration it will help to make research relevant to energy and the environment. The beauty of complexity: It's always relevant.
Posted by at 9:46 AM

10 comments:

  1. The beauty of complexity: It's always relevant.
    Err...did you mean irrelevant?
    ReplyDelete
  2. An Aeroflot airplane made a successful emegency landing on the Neva river in Leningrad (now St Petersburg), Russia, on 21 August 1963. All 52 people on board survived.

    A Wikipedia page in Russian: http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%B0%D0%B4%D0%BA%D0%B0_%D0%A2%D1%83-124_%D0%BD%D0%B0_%D0%9D%D0%B5%D0%B2%D1%83
    ReplyDelete
  3. Ravi Jain, Zulfikar Ramzan, and I actually have a short note with an energy hierarchy theorem. You could fairly dispute whether the energy measure we picked is the "right" one, of course, so we also talk about attributes we would want from a model for reasoning about energy more generally. May be useful, although it's more of a "problem paper" than a solution paper.

    "Towards a model of energy complexity for algorithms"
    R. Jain, D. Molnar, Z. Ramzan
    IEEE Wireless Communications Networking Conference (WCNC) 2005
    http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1424799

    Krishna Palem also has an interesting energy complexity model. He's developed it in the context of analyzing "probabilistic circuits" where each gate is correct with probability p, and gives the wrong result with probability (1-p).

    "Energy Aware Computing through
    Probabilistic Switching: A Study of Limits"
    K. V. Palem, IEEE Trans. Computing September 2005
    http://www.cs.rice.edu/~kvp1/pubs/palemIEEE.pdf
    ReplyDelete
  4. In most physical models of computation, energy is just proportional to 1/time. So if what you mean is energy in the physical sense, I don't see how to get new complexity theory out of this.

    Cris
    ReplyDelete
  5. There was an interesting paper in CCC'07 that was concerned with energy complexity for circuits:

    http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=4262737&arnumber=4262761&count=39&index=23

    In that paper, the energy complexity of a circuit on an input x is defined as the number of gates that output "1" during the circuit's evaluation on x. (This measure is supposedly motivated by neural circuits in the brain.)

    This is a natural notion that isn't directly correlated with circuit size or depth. However, the authors point out that in an electrical circuit it seems to take about as much energy to output "1" as it does to output "0"... maybe there is newer hardware that has this energy-consuming asymmetry?
    ReplyDelete
  6. Another way to approach energy is to say that since computation can be made reversible (http://en.wikipedia.org/wiki/Reversible_computing), there is no minimum energy for computation. But this at least as unsatisfying as just saying that energy is proportional to time. I think that it is not at all intuitive that energy seems to be a trickier resource than time and space.

    Kirk Pruhs
    ReplyDelete
  7. There has been substantial interest in theoretical models of energy consumption, especially in connection with VLSI models.

    In particular Gloria Kissin wrote a PhD dissertation on it (University of Toronto, 1987), some results presented in conferences, notably STOC 1982. There is also a JACM paper
    ( Volume 38 , Issue 1 (January 1991)).
    ReplyDelete
  8. The claim that this is the first successful water landing sounds very unlikely to me, given that in none of the articles in the NYT, to which you linked, do they make such a claim.
    ReplyDelete
  9. Shortly after the Aeroflot incident indicated by Anon#2, a Spanish commercial flight 'landed' in the sea (in Spain we actually have a verb for 'sea-ed'); all passengers survived except one who suffered a heart stroke, while awaiting the rescuers at the airplane door. Due to this death the pilot was under trial. More here (in Spanish):
    http://tinyurl.com/8ov7ms
    ReplyDelete
  10. 1. Dan Bernstein's work on circuits for integer factorization takes an interesting approach to cost complexity, i.e., optimizing the circuits to minimize the amount of dollars that it takes to factor an integer of a given size, where dollars is related to the amount of hardware built and the time to factor one number. We're talking about using billions of processors running for years, to factor a 300 digit number, that sort of thing.

    2. http://en.wikipedia.org/wiki/Water_landing#Survival_rates_of_passenger_plane_water_ditchings lists a bunch of water landings of commercial flights.
    ReplyDelete

Subscribe to: Post Comments (Atom)