Saturday, April 12, 2008

A few links

I've been at ICDE in Cancun for the last few days because of this, and it's hard to blog too much from "the best beach in Mexico". There are some interesting trends emerging from this conference, many of which might be interesting to algorithms folks, and I'll try to say more about this later on.

Two links that came across Google Reader and might be of interest:
  • "Shut up and calculate", by Max Tegmark (via Mathematics under the Microscope). Tegmark argues for an extreme Platonic position: not only is the universe governed by mathematics, but that it is mathematics ! There's more to this argument in the (short) paper: buried in there is an interesting robust variant of falsificationism:
    For a theory to be falsifiable, we need not be able to observe and test all its predictions, merely at least one of them
  • Via BB, New Scientist's list of the ten weirdest computing models (for actual computing, that is). They start off tamely with optical and quantum computing, and then move on into slightly more esoteric models like DNA computing, culminating with ooze computing and water wave computing (hey, I'm on a beach here, computing my legs off!). One of the more interesting proposals was something called 'reversible computing':
    Every computing operation involves feeding inputs into logic gates, which produce output signals. Instead of discarding the energy of those signals, Frank's gates run in reverse after every operation. That returns the energy of the output signal to the start of the circuit where it is used to carry a new input signal
    Of course, what's not clear to me is why this isn't a poor cousin of quantum computing, where as far as I understand all computations prior to a measurement are reversible.
But the idea of reversible computing gets back to very deep ideas about entropy and the second law of thermodynamics. Think of a box partitioned into two parts, each containing air at the same (global) temperature. In the partition is a small passage, guarded by a tiny demon, who only lets molecules go from left to right if they are hotter than average, and from right to left if they are colder than average. Over time, the right side of the container gets hotter and hotter, and the left side gets colder and colder. This demon is Maxwell's demon, posited to try and find a contradiction in the Second Law of Thermodynamics.

One of the more famous refutations of this apparent paradox was by Leo Szilard, who argued that in order for the demon to do its job, it must somehow gather information about the average temperature, and this gathering of information costs energy. Rolf Landauer famously showed in 1960 that reversible computations need not increase thermodynamic entropy (and also information entropy), and these facts were expanded by Charles Bennett to argue that eventually, a demon that does the desired job must run out of space and start deleting information, an irreversible (and therefore entropy increasing) operation. It's a streaming algorithm !!

There's a book that collects all this work together: Maxwell's Demon 2: Entropy, Classical and Quantum Information, Computing. It's been on my list of 'books to read' for a long time now.

7 comments:

  1. Suresh,

    what do you think about ICDE policy of at least one registered attendant per paper?

    Robi.

    ReplyDelete
  2. Have you read the extended version of the "Shut Up and Calculate" paper? Fig 1: A hierarchy of the sciences, which places physics near the root of hierarchy and places computer science towards the leaves. It's actually sandwiched just below electrical engineering and just above psychology.

    Ouch!...I would put computer science at the root of the tree with mathematics...

    ReplyDelete
  3. Hi Robi,
    I don't think I have anything to say per se. Is it a hitting set (one author per paper) or a multiset (each paper is a distinct instance) ? It seems reasonable to require that every paper have a presenter, who should register.

    As for the full version of 'Shut up and Calculate', ouch is right ! Frankly, I don't expect many people to "get" that computer science (or at least theoryCS) is far deeper than just playing with computers, so I'm disappointed, but not surprised.

    ReplyDelete
  4. Suresh,

    Yes, it is reasonable to _expect_ that every presenter registers (in fact every attendant). But to _require_ it formally, not to mention have people spend (waste?) time enforcing it is different, and made me feel awkward. (Disclosure: I have a paper in this ICDE too, but could not attend--my coauthor presented it.)

    BTW, they required a distinct registrant per paper (what you called a hitting set), which means it's not a courtesy reminder to the authors.

    Robi.

    ReplyDelete
  5. I guess I don't feel very strongly about the mandatory registration issue. Since *someone* needs to present the paper, it doesn't cause any major hardship, and it's possible this comes as a reaction to no-shows at earlier incarnations of the conference.

    ReplyDelete
  6. I *did* find the registration requirement an irritant. I try to minimize my travel, so sometimes send several papers to the same conference. I had two submissions accepted to ICDE (one poster, one full). Fortunately, I had a coauthor on one who was also prepared to accept the hardship of traveling to Mexico, who could link a registration to the second paper. Otherwise, things could get tricky. Essentially, one needs to solve a distributed matching problem. At around $750 each, these registrations are no small matter.

    I have no problem with requiring a cover, but a matching seems excessive. Esp when the conference accepted 110 papers + about 200 more posters: that's a lot of reg fees that IEEE is guaranteeing itself there.

    Graham

    ReplyDelete
  7. So I misunderstood then. I think a 'matching' requirement makes no sense, and a 'covering' requirement is a lot more reasonable. If in fact ICDE is requiring the former, then I agree with Robi that this is crazy.

    ReplyDelete

Disqus for The Geomblog