tag:blogger.com,1999:blog-3722233.post7668673731490437787..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Planes. Fellows. Power.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-27801687292053938102009-01-22T23:05:00.000-06:002009-01-22T23:05:00.000-06:001. Dan Bernstein's work on circuits for integer fa...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.<BR/><BR/>2. http://en.wikipedia.org/wiki/Water_landing#Survival_rates_of_passenger_plane_water_ditchings lists a bunch of water landings of commercial flights.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79416114612675738992009-01-21T01:43:00.000-06:002009-01-21T01:43:00.000-06:00Shortly after the Aeroflot incident indicated by A...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): <BR/>http://tinyurl.com/8ov7msBalquihttps://www.blogger.com/profile/09857844891905542749noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67679195246156325642009-01-19T08:40:00.000-06:002009-01-19T08:40:00.000-06:00The claim that this is the first successful water ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74936882064022438402009-01-18T23:24:00.000-06:002009-01-18T23:24:00.000-06:00There has been substantial interest in theoretical...There has been substantial interest in theoretical models of energy consumption, especially in connection with VLSI models.<BR/><BR/>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<BR/>( Volume 38 , Issue 1 (January 1991)).CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63495984034966929112009-01-17T16:05:00.000-06:002009-01-17T16:05:00.000-06:00Another way to approach energy is to say that sinc...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. <BR/><BR/>Kirk PruhsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-663370355109623222009-01-17T13:16:00.000-06:002009-01-17T13:16:00.000-06:00There was an interesting paper in CCC'07 that ...There was an interesting paper in CCC'07 that was concerned with energy complexity for circuits:<BR/><BR/>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=4262737&arnumber=4262761&count=39&index=23<BR/><BR/>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.) <BR/><BR/>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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13114332850619227492009-01-17T11:59:00.000-06:002009-01-17T11:59:00.000-06:00In most physical models of computation, energy is ...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. <BR/><BR/>CrisAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31628875358229021272009-01-16T14:16:00.000-06:002009-01-16T14:16:00.000-06:00Ravi Jain, Zulfikar Ramzan, and I actually have a ...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.<BR/><BR/>"Towards a model of energy complexity for algorithms"<BR/>R. Jain, D. Molnar, Z. Ramzan<BR/>IEEE Wireless Communications Networking Conference (WCNC) 2005 <BR/>http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1424799<BR/><BR/>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).<BR/><BR/>"Energy Aware Computing through<BR/>Probabilistic Switching: A Study of Limits"<BR/>K. V. Palem, IEEE Trans. Computing September 2005<BR/>http://www.cs.rice.edu/~kvp1/pubs/palemIEEE.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76296247635067229412009-01-16T14:03:00.000-06:002009-01-16T14:03:00.000-06:00An Aeroflot airplane made a successful emegency la...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. <BR/><BR/>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%83Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24920488656092860042009-01-16T11:48:00.000-06:002009-01-16T11:48:00.000-06:00The beauty of complexity: It's always relevant.Err...<I> The beauty of complexity: It's always relevant.</I><BR/>Err...did you mean irrelevant?Anonymousnoreply@blogger.com