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:
0 comments. Share your thoughts » 0 comments about this story. Start the discussion »