Stuff to read while you wait around for finals and the Christmas holidays:
- Via alea one of the odder invocations of NP-completeness: Rowing and the Same-Sum Problem Have Their Moments
- An update on the status of US science funding for the next budget year at Computing Research Policy Blog
- An interesting paper is out on < a href="http://arxiv.org/abs/0911.3635">Quantum Metropolis Sampling. The key insight (slaps head) in getting a Metropolis like algorithm to work is not to make a full energy measurement but to only reveal a small bit of the information relevant for whether to accept or reject the move. I spent many an hour trying to figure out how to get around the energy measurement step, so I personally really like this paper. Of course, calling this an “efficient” quantum algorithm seems kind of strange to me because I’d reserve that word for algorithms that converge in polynomial time, and when the spectral gap of the map is exponentially small this sampling will take an exponential amount of time.
- A discussion of computational complexity and economics. See especially the comment by JK.