Here I was just mentioning open problems a few days ago, and in a little example of synchronicity there have been a couple of recent posts on other blogs describing instances of open problems.

Ken Regan, guest posting at Computational Complexity, poses a problem asking how many gates are required in a circuit which computes a ‘garbage collection’ function. The motivation behind the problem (speaking very generally) is that before we can even begin to think about the likes of P vs. NP, we ought to be developing techniques for proving super-linear lower bounds on much simpler problems.

Mark Chu-Carroll at Good Math, Bad Math describes an open problem in graph theory called the reconstruction conjecture. This conjecture postulates that any finite graph with at least 3 vertices is uniquely determined (up to isomorphism) by its vertex-deleted subgraphs. Mark has been doing a nice series of posts on the basics of graph theory leading up to this one.

I’ve never been good at thinking about computation in terms of circuits, and likewise graphs are baffling to me (these facts are perhaps not unrelated), so I’m not going to be losing any sleep over either of these problems. However, that pigeonhole subset-sum problem over at the Open Problem Garden has really gotten under my skin. I’m beginning to think that maybe having a collection of open problems isn’t such a good idea–it’s a great time sink that will keep you from doing all the things you’re supposed to be doing!

Update:

7/13/07: Bill Gasarch at Computational Complexity has a post plugging the Open Problem Garden. Maybe we have a little momentum building now…

7/17/07: And here is one more open problem post: Michael Mitzenmacher asks for codes for a Poisson-repeat channel over at My Biased Coin.