Category Archives: Computer Science

A Breakthrough Donation for Computer Science

Lance Fortnow has a post summarizing some of the news affecting the CS community over the past month, including updates on various prizes as well as the significant media attention focusing on physics- and math-related topics such as movies about Turing and … Continue reading

Posted in $$$, Computer Science, Prize | 5 Comments

Error correcting aliens

Happy New Year!  To celebrate let’s talk about error correcting codes and….aliens. The universe, as many have noted, is kind of like a computer.  Or at least our best description of the universe is given by equations that prescribe how … Continue reading

Posted in Astrobiology, Computer Science, Extralusionary Intelligence, Off The Deep End | 10 Comments

Simple circuit "factors" arbitrarily large numbers

Last Thursday, at the QIP rump session in Beijing, John Smolin described recent work with Graeme Smith and Alex Vargo [SSV] showing that arbitrarily large numbers can be factored by using this constant-sized quantum circuit to implement a compiled version … Continue reading

Posted in Computer Science, Hype, Quantum Computing, Quantum Computing Bastardizations | 3 Comments

What increases when a self-organizing system organizes itself? Logical depth to the rescue.

(An earlier version of this post appeared in the latest newsletter of the American Physical Society’s special interest group on Quantum Information.) One of the most grandly pessimistic ideas from the 19th century is that of  “heat death” according to … Continue reading

Posted in Computer Science, General, Mathematics, Physics, Science | 6 Comments


Recently computer scientist Leslie Valliant won the ACM’s Turing Award, considered one of the most prestigious prizes in computer science. Valliant is famous for many results, not the least of which are his results on the Permanent of a matrix. … Continue reading

Posted in Computer Science, Mathematics | 5 Comments

BPP^(Wolfram Alpha)

Via @fortnow, Wolfram Alpha is now offering answers to classical complexity queries (see blog post at the WolframAlpha Blog).

Posted in Computer Science | 2 Comments

US Quantum Computing Theory CS Hires?

I’m trying to put together a list of people who have been hired in the United States universities in CS departments who do theoretical quantum computing over the last decade. So the requirements I’m looking for are (a) hired into … Continue reading

Posted in Computer Science, Quantum Computing, The Loony Bin Called Academia | 15 Comments

TQC 2011 and a Bonus! Rant!

So most of my conference announcements are going out on qspeak now (and will be digested every week in a post here.) But since I’m helping out with this one it, I thought I’d post a separate note here. TQC … Continue reading

Posted in Computer Science, Conferences, Quantum Computing | 6 Comments

Consequence of the Concept of the Universe as a Computer

The ACM’s Ubiquity has been running a symposium on the question What is Computation?. Amusingly they let a slacker like me take a shot at the question and my essay has now been posted: Computation and Fundamental Physics. As a … Continue reading

Posted in Computer Science, Go Ahead, Waste Your Time, Off The Deep End, Physics, Quantum Computing | 4 Comments

Does Not Compute

Okay, last one. But damn I could make these movies all night and it would make me laugh and all of you cry:

Posted in Computer Science, Extralusionary Intelligence, Off The Deep End | Leave a comment