Burnt Carmel

Three (pseudo-)random updates:

First, sadly, I’ll be going to neither ICS’2011 in Beijing nor QIP’2011 in Singapore this coming week—too much travel!   If you’re going to either conference and would like to contribute a guest post, please let me know.

Second, I posted a note to the arXiv this week called Impossibility of Succinct Quantum Proofs for Collision-Freeness.  Here’s the abstract:

We show that any quantum algorithm to decide whether a function f:[n]→[n] is a permutation or far from a permutation must make Ω(n1/3/w) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation.  This implies that there exists an oracle A such that SZKA⊄QMAA, answering an eight-year-old open question of the author.  Indeed, we show that relative to some oracle, SZK is not in the counting class A0PP defined by Vyalyi.  The proof is a fairly simple extension of the quantum lower bound for the collision problem.

This result is neither hard nor surprising, but it does more-or-less solve a problem that’s bothered me since grad school (and which I mentioned a couple months ago on this blog) in a ridiculously simple-in-retrospect way, which is either nice or disappointing depending on how you look at it.

Third, some of you might have heard that the Carmel region in Israel recently suffered a terrible forest fire, which destroyed about 30 million trees and killed 44 people, and which required the assistance of many countries to put out.  Yesterday, after giving a talk at the Technion in Haifa, I had a chance to tour some of the fire damage.  While we were on the hike, a torrential downpour started (which caught me without coat or umbrella)—if only the rain had come a few weeks earlier!  Anyway, here are some photos:

21 Responses to “Burnt Carmel”

  1. Anonymous Says:

    Liked the last picture.

  2. John Sidles Says:

    I can’t say much that’s sensible about the loss of life in the Carmel fire … nor about the long, sad history of religious factions in the Middle East … nor even about oracle-dependent separations among complexity classes.

    But it may help to reflect, that the torrential rain that fell upon you, while you and your friends walked in the ashes of the fire, was a great blessing.

    My wife’s own favorite place in all the earth, a small natural area near our campus, suffered a similar fire … and now, two years later, the area where the fire burned provides the richest natural habitat of the entire natural area.

    Under the ashes of the Carmel hills, buried in the soil, are seeds that have been awaiting, twenty years and more, just such a fire and just such a rain. So if you visit the same area in two years, you will be impressed … in ten years, you will be gratified … in twenty years, astounded … and yes, in fifty years, you will see ashes again.

  3. anonymous Says:

    John, you forgot to point out the strong connection of the Carmel fire to Kahler manifolds, and that the fire proves beyond a doubt that quantum simulation is of polynomial complexity.

  4. John Sidles Says:

    LOL … thanks anonymous … yes, Google’s Ngram Viewer shows us that usages relating to geometric dynamics are trending steadily upward … good! 🙂

    Moreover, you and I are in reasonable accord, that in pretty much any STEM discipline, moderate levels of cynicism are distinctly preferable to increasing levels of apathy. 🙂

  5. John Sidles Says:

    In Scott’s phrase, here’s a “(pseudo-)random” confection relating to next week’s TEDx conference at CalTech, Feynman’s Vision: the Next Fifty Years, at which Scott and many other QIT luminaries will be speaking.

    This is the kind of conference at which the speakers set forth roadmaps. It turns out that Google’s Ngrams Viewer is a pretty handy tool for assessing roadmaps … let’s use it for this purpose.

    Let’s pick “malaria eradication” as an ngram associated to a 20th century roadmap … this particular roadmap ngram achieved its peak relative incidence of 2×10^-5 in the year 1965.

    Here’s a (pseudo-)random selection of other roadmap ngrams that achieved a peak relative incidence of order 2×10^-5: smallpox eradication, malaria eradication,S matrix, endrin, fusion power, satellite power, bubble memory, cold fusion, extrasensory perception.

    Hmmm … it’s interesting to see that roadmap ngrams can persist for decades even in the face of adverse STEM findings (cold fusion) … and conversely, that roadmap ngrams can go extinct by reason of spectacular success (smallpox eradication).

    Other fun questions to ask are, whose ngram is more popular, “John von Neumann” or “Richard Feynman”? The answer is … both ngrams are mighty popular! 🙂

    These mainly-for-fun ngram surveys are broadly consonant with the common impression that von Neumann and Feynman were two of the greatest STEM roadmappers of the 20th century. It will be great fun to watch the TEDx attendees try to match their record.

  6. Raoul Ohio Says:

    Ngrams are an interesting tool for assessing the history of concepts, but a blunt tool. Consider “cold fusion”. The term, presumably coined by the Fleischmann/Pons group, has at least three components, with varying frequency histories.

    1. As reported as news, a huge scientific breakthrough.

    2. In debates: could it possibly work?

    3. A long afterlife as a poster child for scientific dingbattery.

  7. John Sidles Says:

    Google’s ngrams are not Alethian oracles that tell us the truth … neither are they Athenian oracles that teach us wisdom … rather they are Clionian oracles that teach us history.

    As for finding truth and wisdom in history … well … the gods have never helped us humans much with that. 🙂

  8. John Sidles Says:

    If anyone attending QIP2011 cares to report on the talk by Poulin, Qarry, Somma and Verstraete,
    Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
    , or on any of the other QIP talks, this would be of very great interest to me (and many).

  9. santana Says:

    Good choice you are not attending ICS’2011. either way you will not admit to it but as scholar u ought to be committed to certain values such as human rights that all sponsors of ICS do not adhere to.

  10. John Sidles Says:

    In raising our children, my wife and I discovered that they remembered our behavior much longer than they remembered our advice.

    Similarly, history suggests that there’s not much to be gained by overlaying scientific meetings with “official” political doctrines and declarations … because what the attendees really believe is told loud-and-clear by their actions.

    The participants in international meetings like ICS’2011 and QIP’2011 provide the world with memorable examples of cooperation and amity … as does Scott and everyone else who hosts open-forum weblogs. Good.

  11. Simon Lukewarm Says:

    Dear John,

    Sometimes I really wished you knew what you are talking about. Why don’t you visualize the following scenario.

    There is an “international meeting” taking place in 1942 hosted by a university that is entirely sponsored by the Nazi Regime. Would you attend ?

    John, it is somewhat naive to label things as they appear on first glance without critically observing the underlying factors.

    This blog is not meant to attack people neither institutions nor is it intended to stir up bad sentiment. The post by Santana raised an adequate point which obviously by passed moderation in good faith.

  12. John Sidles Says:

    Simon, I was just pointing out that (historically) actions and stands taken by individuals have (arguably) exerted a greater effect than actions and stands taken by organizations.

    Ed Wilson’s recent novel Anthill is an extended meditation upon these difficult moral questions (p. 348):

    Raff lived by three maxims. Fortune favors the prepared mind. People follow someone who knows where he’s going. And control the middle, because that’s where the extremes eventually have to meet.

    What Wilson is suggesting in Anthill—and to his credit, he works through the scientific, social, and personal implications in an integrated, natural way—is that a question like “What is math and science?” has a broad range of feasible answers, among which one is “They are collective activities of primates.”

    When we contemplate the burnt hills of Carmel and all that the burning means, or we similarly contemplate (say) the destruction of the mathematics community at Hilbert’s Göttigen, then we are led to take Wilson’s line of reasoning seriously.

  13. Simon Lukewarm Says:

    John, while it may sound instructive to quote a novelist who has done empirical work on these issues it sounds to me more like citing a defunct philosopher. These are real issues that need to be dealt with pragmatically. Applying a Woodrow Wilson agenda to them will lead to exploitation. It is just naive to follow your line of reasoning or argumentation …

    your participation in something funded by a regime that essentially boycotts human rights tells me a lot. Your continued participation and acceptance of honoria tells me a different things. your acceptance of such events is ultimately what tells me who you really are as a person.

    but i will surrender any further debate on this topic. santana made a good point.

  14. John Sidles Says:

    Simon, it made me smile to see Ed Wilson called a “novelist” 🙂

    It is largely thanks to leading scientists like Wilson and Goodall, that serious analyses of human cognition, religion, morality and politics no longer ignore human evolutionary history.

    We all gain by this … both WIlson and Goodall “saw what everyone had seen, and thought what no one had thought”

    Moreover, both Wilson and Goodall are politically active … their efforts focus on conservation, sustainment, and peacemaking … and they both think ahead, on timescales of centuries and millennia, and act with foresight. Good.

  15. Raoul Ohio Says:


    Given your concern about “a regime that essentially boycotts human rights”, you might find it illuminating to spend a week each in the streets of Mogadishu, Tehran, and perhaps Pyongyang, for some “real world experience”. It might be wise to leave a will.

  16. Raoul Ohio Says:

    A brief intermission for a WhoDaThunkIt: About 500 times a day, thunderstorms shoot beams of antimatter into space:


  17. John Sidles Says:

    Simon, your post and Santana’s occurred to my mind when I compared two recent books: Istvan Hargittai’s biography Judging Edward Teller, contrasted with Jon Cohen’s Almost Chimpanzee.

    Hargittai’s scholarship is impeccable … his is perhaps the finest biography of Teller that will ever be written. And yet, the men and women in Hargittai’s narrative are (in essence) always described as angels — some fallen, some not. According to everything we know of human cognition, biology, and evolutionary history, this traditional view of “the angels of our nature” (to borrow Lincoln’s phrase) is so limited in scope, as to be grossly incorrect.

    Jon Cohen’s Almost Chimpanzee is a popularization and update of classic works like Frans de Waal’s Chimpanzee Politics … and to Cohen’s credit, he describes chimpanzees and the researchers who study them with equal interest and dispassion.

    When the scientific, political, technological, economic, and moral history of the 21st century is written … these two perspectives will merge … and this merging will be a mighty interesting process.

    An essayist who writes engagingly on this topic is David Brin.

  18. Jim Lee Says:

    Hi Scott,

    My heart goes out to the friends and families of those who lost their lives in that tragic fire. I am also saddened by the loss of all the land, trees and wildlife. I used to live in Oregon when the “Biscuit Fire” blackened over 500,000 acres of pristine wildlands, destroyed homes and wildlife and left a cloud of smoke over the entire area for about a month. No mercy should be shown to those who started these fires. This is inexcusable!

  19. John Sidles Says:

    I am hoping that Shtetl Optimized will become more lively, in the event that Scott live-blogs his lecture at the TEDxCalTech Event, Feynman’s Vision: the Next 50 Years, which takes place tomorrow (Friday) at CalTech.

    Scott’s has titled his lecture Physics in the 21st Century: Toiling in Feynman’s Shadow. Hmmm … I dunno … fifty more years of “toil” sounds kinda dark … hopefully at least some of the TEDxCalTech speakers will echo the memorable words of Steve Martin’s character Navin R. Johnson:

    Waiter, take away these old STEM Roadmaps … bring us some *fresh* STEM Roadmaps! The freshest you’ve got. This year!

    Because heck … don’t pretty much *all* of Feynman’s most famous lectures lay out fresh STEM roadmaps?

    Seriously, we should all admire the courage of the speakers for even taking the stage at this event … because they’re going to have to share that stage with none other than Kongar-Ol Ondar:

    Kongar-Ol Ondar (Tuvan: Коңар-өл Ондар) is a master Tuvan throat singer and a member of the Great Khural of Tuva.

    As Feynman might have said … it’s gonna be terrific! 🙂

  20. Raoul Ohio Says:

    A brief interrupt about the future of computing: Most participants on SO are interested in computing, and probably many get Bruce Schneire’s newsletter. This month Bruce reviews what went down in the last 10 years, and gives his guesses about the next 10 or so. Check it out:


    Although I come from a different direction than Bruce on some issues, I find that when I read his analysis of anything, I usually think: “obviously”.

  21. Raoul Ohio Says:

    News flash from the nonassociative division algebra frontlines: MS Word spell check suggests “octomoms” for “octonions”