A Search Meme

October 26, 2007

David Ng of The World’s Fair has been playing with viral marketing and Google bombing, and the experience has given him an idea for a nifty new meme. The way it works is this: Try to come up with 5 different search phrases for which, when entered into Google, your blog is the number one hit. The search phrase can be enclosed in quotes if necessary, but obviously it is even better if it works without the quotes. A commenter at David Ng’s post (and by the way, read those comments at your own risk–some of them aren’t pretty) suggests scoring the search phrases based on the number of hits. So, the ideal search phrase would have your blog being number one out of something like a million hits returned.

As it turns out, this is much easier to do than it might sound. Looking back at my previous post, Steven Pinker’s formula gives an estimate of the number of distinct sentences one can utter, which comes out to be the enormous value of 1020. Given that, it is perhaps not too surprising that we might have some catch phrases that appear more or less uniquely in our writing. (The key to getting the hit counts high at the same time is to have those catch phrases made up of a few words that individually are common.) So without further ado, here are some search phrases that (as of this writing) give this blog as the number one hit:

Each of those searches returns more than 100,000 hits. I’ll add one more search string for good measure, even though it only returned a few hundred hits, because it links to one of my favorite posts (and because at heart I’m a nasty person): Bringsjord parody.

So that’s it. Consider yourself tagged if you’re so inclined, and have fun playing with search strings!

What is your formula?

October 23, 2007

[Note: I goofed up in describing What is your formula? as an Edge annual question. It's not, and I've updated the post below to correct this.]

Edge Foundation does a yearly thing where they pose a question to an array of scientists and other intellectuals, and collect together all their answers. They have also had occasion to pose a question outside of the normal cycle, when after the 9/11 terrorist attacks they asked, What Now? Earlier this month, as part of a collaboration with the Serpentine Gallery in London, Edge posed another question to their collection of thinkers. The question was What is your formula? Your equation? Your algorithm? and browsing through the answers is a great way to waste an afternoon. Because the replies consisted mainly of diagrams and equations (many of which were hand-drawn), they are displayed as scanned images, which adds a personal touch to the results.

Unfortunately, the format of the question also limited the form the answers could take, most of which express some kind of heuristic relationship rather than a true formula. I did like this entry by psychology professor Danny Kahneman, which seems to explain a lot of popular culture.

As might be expected, the entries by mathematicians tended to have actual formulas in them. I can relate to the sentiment expressed by Nassim Taleb in his entry. Over a typeset page of equations on how to price stock derivatives, he hand-wrote, “I spent a large part of my life working on this equation. I am glad it is over.”

Many of the entries were just plain silly. I’ll single out this one by cognitive scientist Donald Hoffman, because of his abuse of mathematics. He has a nice diagram illustrating composition of functions that would make any algebra teacher proud, but follows it with a fallacious argument that shows he has not mastered basic logic.

Let me mention one more entry before I stop. Popular math writer Keith Devlin uses an analogy to speculate on how math will be taught in the future, and it looks like he would like to see virtual manipulatives taken to a whole new level.

Be sure to also check out the archive of annual answers to questions. Because they are not constrained by the “formula” format imposed on the current question, the answers are better developed and far more insightful.

SocialRank (and MathBloggers) is now live

October 1, 2007

A few weeks ago I wrote a post about SocialRank, which seems to be a new blog search engine that identifies which blogs entries are currently generating a lot of interest. These entries are categorized by subject matter and daily ‘top 15′ lists are created for the top blogs and top blog entries. The result for each category appears under its own domain name, and for math blogs the end product is MathBloggers.

At the time I last wrote about this, the SocialRank sites were all password protected while under development, but an anonymous commenter has pointed out that as of today SocialRank is now live. The first 30 blog categories are now open, and this includes MathBloggers.

So how good of a job did MathBloggers do on its first outing? Well, in addition to several blog entries that I had already read and might expect to see on a ‘top 15′ list, there were several entries (and blogs) listed that I was not familiar with. So MathBloggers succeeded in broadening my reading. The MathBloggers list also included a nice mix of pure math, math ed, mathematical physics, and theoretical computer science blogs. The blog Good Math, Bad Math, while being a very good blog, seemed to be over-represented on the list, so SocialRank may need to fine-tune their ranking system to keep very popular blogs from overwhelming the little ones. There was also one noticeable bug: blog URLs only contained the actual domain name and not any path info. As a result, Good Math, Bad Math shows up as ScienceBlogs, for example, and Jacques Distler’s Musings appears simply as the host server name Golem. (This problem did not affect the URLs for individual blog entries, only for the blog home URLs.)

Overall, it seems like an interesting effort, and I’m going to keep checking MathBloggers on a regular basis to see how it develops.

Update

Hmmm, maybe I spoke a little too soon on this. There is definitely something a little “off” about the Top Blog Posts list. A couple of entries currently listed there are from Skrentablog, which is a tech blog with practically no math content. The other blogs represented on the list seemed to fit the category better, but some of the particular entries seemed like peculiar choices. Vlorbik wonders how his own blog got so highly rated. His particular entry that made the list was about the Excel number formatting error that was a big news item last week; maybe the overall blogosphere interest in the story somehow rubbed off indirectly on his post. In any event, the SocialRank ranking algorithm seems to be doing some weird things. It will be interesting to see how well it tracks blog interest later this week when the next Carnival of Mathematics comes out.

Carnival of Mathematics XVI

September 8, 2007

Welcome to the 16th Carnival of Mathematics, the comments and opinions edition. The host of the previous edition of the carnival set up some pretty high expectations, what with providing both interesting background information on the fortnight’s posts, and pretty pictures to accompany them. We’ll be having none of that here. No, this is the blogosphere we’re talking about, and even if the subject matter is the noble quest for mathematical knowledge, our stock and trade are comments and opinions. That high bar actually has me thinking “limbo”, and I want to see just how low I can go. So without further ado, here are this edition’s entries.

The Good

I have nothing but admiration for the good souls who struggle day after day with teaching our children, so we begin our list with the mathematical educators

Starting us off is Denise at Let’s play math!, who gets us in the mood with quotations on the joy of mathematics. This batch of quotations ends with the line from G.H.Hardy, “Beauty is the first test: there is no permanent place in this world for ugly mathematics.” We’ll see about that; I’m pretty sure that some ugly mathematics (or is that ugly mathematicians?) lie in wait for us a bit later. But I digress… Denise then gets to the meat of pre-algebra problem solving with posts on the tools and 2nd grade. In the comments to that first post, commenter Bill Howdle describes a (long ago) homework math problem that he was unable to help his daughter with, and after 25 years it still nags at him!

Probably everyone here has heard at some point the story of how, as a young child, Gauss discovered a formula for the sum of the first n positive integers. In Pairing up with Gauss, Math Mom describes how she teaches this to 10- to 12-year-old kids, using different arithmetic progressions to reinforce the pairing technique. While you’re visiting, be sure to also check out the link she provides to an American Scientist article which dissects the Gauss myth.

For our next entry, Dave Marain of MathNotations shows how to find the Golden Ratio in the geometry of a certain isosceles triangle, in Searching for Gold in Geometry. Be sure to scroll down through the comments (this will be a recurring theme in this edition) to read Eric Jablow’s nifty introduction to algebraic number theory.

If someone poses a problem about a random number between 1 and 10, I think it’s safe to say that everyone would assume that the number is going to be uniformly distributed. But what if we’re talking about some random mathematical object where there is not an obvious, intuitive choice for the distribution? Jonathan discusses What is a random triangle? over at jd2718. The post is short, but (you guessed it) much discussion is generated in the comments.

To end this category, Jonathan also recommends reading Pissed Off’s discussion of whether partial credit should be given on math tests. Now, having spent some time grading student exams, I’m a big fan of multiple choice questions–preferably using one of those machine-readable bubble answer sheets so that one doesn’t even have to look at the students’ work. Pissed Off, to the contrary, seems to be basing her opinion on what might be best for the student and not the instructor!

The Bad

Next up for your viewing pleasure are the mathematicians, either as the subjects or the authors of blog entries…

John Kemeny of A Mispelt Bog has a nice post about an obscure result relating to patterns of digits in repeating decimals, that has recently been getting renewed attention. In The Secret Theorem of M. E. Midy = Casting In Nines, he tells how Midy’s theorem has recently been rediscovered and extended. John is also offering up a short post looking at some statistics on Ph.D. graduation rates and SAT scores by state.

Next, John Armstrong of The Unapologetic Mathematician takes a break from his ongoing series on category theory to respond to a question that reader posed in a comment. In A little aside on linear algebra, John discusses the relationship between inner products, norms, and the choice of a basis in vector spaces.

Hmmm, only two math submitters this edition? Well, that just won’t do, and fortunately there has been some other juicy math blogging recently that we can highlight.

Let’s start with the low-brow… I’ve often thought that the way to attract more public interest in mathematics is, like just about everything else that is “marketed” these days, to sex it up a bit. The New York Times helped out in this regard with an article describing an argument by UC Berkeley mathematician David Gale, that the commonly reported statistics on male and female sex partners cannot possibly be correct. This was all over the blogosphere last week, but since no one else has submitted a relevant entry, I’ll suggest taking a look at Men and Women Cannot Can Have Different Average Numbers of Sexual Partners by Jake Young at Pure Pedantry. Jake gives a nice recap of the arguments back and forth, and has so many updates based on reader comments that I lost count. The very first commenter gives a nice little example of how, while the means must be equal, the medians definitely might not.

For something a bit more high-brow, I’d recommend Ben Webster’s post at the Secret Blogging Seminar on Zeta function relations and linearly equivalent group actions. Ben mentions that the subject of this post comes from some research he did as an undergrad, and it contains the prettiest looking math blogging I’ve seen recently. But what caught my attention was that the comments were devoted entirely to a discussion of using mathematicians’ names as nouns versus adjectives when referring to eponymous mathematical structures.

To shift back to the low-brow for a mome

nt, I noticed that Ben is also making a call to keep the sarong theorem archive growing. I have to admit that this is a nice picture of Ben, and math ed content is welcome, too.

I recently bought Danica McKellar’s new book, Math Doesn’t Suck, for my daughter. This book has already been the subject of much discussion on the web and I won’t try to add anything here. But I’ve been looking without much luck for a comprehensible explanation of the research paper she co-authored, “Percolation and Gibbs states multiplicity for ferromagnetic Ashkin-Teller models on Z2“. So, I was delighted to see that Terry Tao has done just that in his blog entry “Math Doesn’t Suck”, and the Chayes-McKellar-Winn theorem. Tao gives both a high-level and a fairly detailed explanation of what the theorem means, and also provides some recollections about Danica’s time as a student.

Finally, we close the mathematicians’ portion of our program with Greg Muller at The Everything Seminar railing against the bad math behind a classic gambling scheme that’s “guaranteed” to pay off, in Infinite Series vs. Reason. Specifically, if you are, say, flipping a coin to determine whether you win a bet, and you double your wager after each round, then you’re bound to come out ahead at some point, right? What could possibly go wrong?

The Ugly

Finally, we come to the computer science portion of our carnival…

…and there is nothing better to make the segue from bad math to ugly computer science than the following little brouhaha. Mathematician Neal Koblitz has an article in the September Notices of the AMS in which he criticizes the cryptographic community, and it evidently has many computer scientists up in arms. None of them felt compelled to submit their entries to the carnival, unfortunately; but being the lover of soap opera that I am, I will do the honors. Luca Trevisan at in theory writes about The Swift-Boating of Modern Cryptography, and it goes without saying that you must read the comments on this one. Lots of ugly trash-talking there, but no doubt Koblitz is a bad, bad, naughty mathematician who deserves it all :)

On a more positive note, Julie Rehmeyer at the Science News blog MathTrek has a couple of entries timed just perfectly for this edition. (And Julie is being promoted from math to computer science as well!)

In Squashing Worms, Julie describes research by Microsoft theoretician Jennifer Chayes into how computer worms spread through the internet, in order to calculate which hosts should get patched first to best slow the spread. There may also be implications of this research for biological organisms, and Chayes plans to work with epidemiologists to gain a better understanding of this.

In Julie’s second entry for this edition, Kidney Matchmaking, we learn about new algorithms being designed to match kidney donors with patients needing transplants. An estimated 1,000–2,000 additional patients per year might receive transplants that otherwise wouldn’t, once the techniques are implemented nationwide.

In the comments to Julie’s second post, Suresh from The Geomblog mentions some additional research being done on the kidney transplant matching problem. In fact, he recently did a post on the subject himself, Saving lives with exact algorithms, which deserves its own mention here in the Carnival. The amazing take-home point from Julie’s and Suresh’s posts is that results from the study of algorithms are actually saving patients lives–concrete benefits that one would probably not expect from such an abstract topic.

Most of us are familiar with the history of Euclid’s fifth (parallel) postulate, and how relaxing this requirement allows us to come up with different geometries in which “lines” differ from our usual intuition–for example, lines might correspond to great circles on a sphere. Now, what if we were to really relax the definition of what constitutes a line, to create something that “behaves like” a line but isn’t required to be straight? According to David Eppstein at 0xDE, computational geometers do just this sort of thing, and the result is a pseudoline. However, different researchers have used different definitions for pseudolines, and in his post Was sind und was sollen die Pseudogeraden?, David attempts to clarify some of the resulting confusion about what the proper definition should be.

For our next entry, Aaron Sterling recommends an item from Scott Aaronson’s blog Shtetl-Optimized. In Shor, I’ll do it, Scott gives a plain-language explanation for Peter Shor’s quantum factoring algorithm, which was one of the first algorithmic results exploiting the power of quantum computing. This is an older post, but one of Scott’s most popular ones. Now, the comment section is always lively at Shtetl-Optimized, so it goes without saying that you want to check that out. Aaron mentions that you should particularly look for Robin Blume-Kohout’s comment explaining the Fourier transform.

Finally, Aw, shucks is a very short post by Jeff Erickson at Ernie’s 3D Pancakes. It seems that Jeff has a difference of opinion with Doron Zeilberger over the value and philosophical implications of computer-generated proofs, and these two gentlemen are not shy about, ahem, expressing their opinions. I can’t quite decide if they love each other or hate each other’s guts, but either way you’ve got to follow those links and read what they have to say…it seriously just doesn’t get any better than this.

This concludes the 16th edition of the Carnival of Mathematics. The 17th edition will be hosted on 9/21 over at MathNotations by Dave Marain, who will undoubtedly handle the proceedings in a more timely fashion than moi.

Let me leave you with one final parting link, some words of encouragement from Professor Mark Sapir at Vanderbilt University. Be sure to turn up your speaker and click on the sound file at the bottom of the page!

Tick, tock…

September 7, 2007

I’m feeling a little bit under the weather, so rather than trying to force myself to finish gestating the next Carnival of Mathematics, I’m going to get some rest. But don’t worry, the delivery shouldn’t be more than a few hours overdue.

Let me take this moment to remind everyone that the Blog Carnival submission form will continue to forward submissions to me until midnight tonight, so please do send in those last-minute entries. Or you can email them to me at kurt (at) learningcomputation (dot) com.

And now, back to bed. Zzzzzzzzz.

Math Carnivalia: Present, Future and Past

August 26, 2007

The 15th Carnival of Mathematics is now up at John Kemeny’s A Mispelt Bog, and it looks like a good one. I especially like how he has taken the time to provide some background on the posted subjects above and beyond what was in the post entries themselves. It definitely sets a high bar for whatever poor schlemiel is going to be hosting the next one.

Which reminds me, the 16th Carnival of Mathematics will be hosted by yours truly right here in two weeks, on September 7th. The theme for the next fortnight’s edition will be:

How has the mathematical mindset shaped your self-actualization in a post-postmodern world?

I don’t know about you, but I could write a few thousand words on that without even thinking… Hey, wait, come back! I’m only joking! The Carnival of Mathematics is not a “themed” carnival beyond the mission statement that applies to all editions. The short version, from the Blog Carnival entry for the CoM is as follows:

Everything math-related goes in here: proofs, explanations of basic concepts, puzzles, writings about math education, mathematical anecdotes, refutations of bad math, applications of math, reviews of popular math… Note that sufficiently mathematized portions of other disciplines, especially physics and computer science, are acceptable.

For a slightly longer version, check out Alon Levy’s description at the CoM homepage. And for anyone who’s stumbled upon this page without having encountered the notion of a blog carnival before, more information can be found at Wikipedia.

So, start sending those submissions my way. You can use the Blog Carnival submission form, or you can email your links to me at kurt (at) learningcomputation (dot) com. Please include “CoM” or “Math Carnival” or the like in your subject line so I don’t mistake your message for spam.

Now, I’d like to make a couple of extra requests of you for the upcoming carnival, beyond what may have been done in the past:

First, note that Alon has added a bit of extra instruction for this edition on the submission form:

It’s perfectly acceptable to nominate entries from other blogs. The limit of three posts per individual means that a single blogger may not have more than three posts in an edition; it does not mean you may not nominate many more posts from many blogs or bloggers.

Several people in the past have made the observation that there is a lot of interesting math blogging going on that for one reason or another never gets submitted. I think it was this little exchange with Noah Snyder at the Secret Blogging Seminar that finally convinced Alon to codify this into the carnival description. So if you come across an example of someone else’s math blogging that you think deserves a wider audience, by all means submit it to the carnival. Let me know whether or not you’ve already mentioned it to the author, because I’d like to give them advance notice before linking to them.

Second, when you submit a link to me, please include a paragraph or so describing what the linked post is about. I’ll certainly read through all of the submitted posts, but I know from reading past carnivals that there are some posts for which there is just no way I could do them justice in my own words. Heck, a couple of them might as well have been Greek to me…

Finally, there has been some discussion around the past few editions of the carnival concerning the mix of “math ed” posts and “math research” (for lack of a better term) posts, for example here, here and here. So as a little experiment, I’ll be grouping the submissions by these categories. However, I know from past carnivals that some posts don’t fit cleanly into one category or another, so let me know how you think your submissions should be grouped. If I receive enough suitable entries, I’ll also create a “comp sci” category. The first few carnivals had several submissions dealing with algorithms and computational geometry, but comp sci has been AWOL lately. I’d really like to see that change.

Now if you’ll excuse me, I’m going to return to perusing the 15th edition …

Link this, SocialRank

August 23, 2007

[Update: I thought, since I mentioned Snap Shots in this entry, that I should just turn this feature on in this blog instead of sending you elsewhere. Done. Unfortunately, it turns out not to be a magic bullet, as you'll see if you scroll over the mathbloggers.com link. However, the cached Snap Shots image at The Unapologetic Mathematician that I refer to below still worked the last time I checked.]

I’ve noticed in the past couple of days, trackbacks appearing on many math blogs for a site named mathbloggers.com. Well neat, I thought, a new math blog. Unfortunately, that site is password protected, so clicking on that link is not going to get you very far. However, the site is evidently not shielded from search engines and the like, and if you roll over the trackback link on a blog that has the Snap Shots feature enabled, you can see that it appears to be just a link aggregator site. (For example, as of this writing you can use this post at The Unapologetic Mathematician and scroll to near the bottom of the comments.) There is one other thing, though, and that is the phrase “powered by SocialRank” on the trackback link.

What is SocialRank? On the Snap Shots image I can make out the blurb, “SocialRank brings you the most popular stories that people are paying attention to right now.” If I try Googling “socialrank”, I find a great number of these aggregator sites on all variety of topics, and all apparently password protected. Well now, SocialRank isn’t going to be bringing me much of anything if I can’t get to any sites powered by it… Could this be some bizarre new kind of comment spam? Did someone figure out a new way to hack search engine rankings or something? I tried doing a whois lookup on some of the sites and found that they were registered to someone named Michael Reining at a company called MindValley.

Ah, now we’re getting somewhere. MindValley appears to be a “Web 2.0″ type of company dealing in e-commerce and web marketing and the like, based in Kuala Lumpur. And, they have a blog. On it, they explain a little bit about SocialRank:

We develop breakthrough applications that have the power to be very disruptive. We are currently working on a project called SocialRank that will instantly be able to surface the top blog posts for 1,000 blogging communities online. To help us pull this off, we have hired one of the smartest mathematicians from the leading technical school in India and assembled an all start team of developers. The algorithm is nothing short of breathtaking because for the first time you will instantly be able to see 1) the top stories coming out of every blog community and 2) see which blogs are the hottest right now to see where the conversations are happening online.

So there you have it. I’m guessing that when they feel their product is ready for public consumption, the password protection will come off those sites.

Oh, and that mathematician, a fellow named Talat, has a blog entry with a math anecdote from his youth. Maybe we can get him to submit something to the Carnival of Mathematics :)

A simple plea to all computer scientists

July 25, 2007

I was trying to do a little background reading on a problem in complexity theory (this problem, to be precise), and I was dismayed to find myself thwarted by the unavailability of papers. Not being an academic type, I don’t have ready access to a research library. (I can, in theory, get papers from my local public library via inter-library loan, but it takes a couple of weeks. I can also drive to the nearest university that has a CS graduate program, but I’m not going to count that as “ready access”.) So I depend upon papers being available online, and a lot of researchers are very obliging in this regard. However, there are still a lot of exceptions.

For example, Richard Karp’s 1972 paper “Reducibility among combinatorial problems” [2] does not seem to be online. (By the way, it is of course possible that this or any the subsequent papers I mention are in fact online but I wasn’t thorough enough in my searches. Please let me know if this is the case.) This paper is mainly of historical interest at this point, but it was such an important paper that I’m really surprised by its absence.

Moving forward in time 16 years to 1988, we have another highly cited paper, “How easy is local search?” by Johnson, Papadimitriou and Yannakakis [1]. Again, given how many citations this paper has, I’m surprised no one has been moved to scan it and put it online. (Well, actually, someone has, and I’ll get to that in a moment.)

Going forward another 4 years to 1992 takes us to Woeginger and Yu’s paper “On the equal-subset-sum problem” [4]. Here we’re starting to get recent enough that the authors might still have the source versions of the paper in electronic form. Not to pick on anyone (especially since I’m a fan of his P vs. NP page), but why doesn’t Woeginger include this paper on his publications page?

Finally, for a recent example, we jump forward 11 years to 2003 for a paper by Kellerer, Mansini, Pferschy and Speranza [3]. Given the recent date of this paper I would have thought that it would be a matter of routine for the authors to upload a preprint of it to their web pages.

Out of a total of 9 papers I tried to locate online, I was unable to access 4 of them. The good news is that more than half of the papers were in fact freely available on the web. The bad news is the following: with the exception of the Karp paper, the others are in fact online and they’re for sale at Elsevier’s ScienceDirect. Now, I have nothing against capitalism, and I actually think it’s great that these articles are available for sale on an individual basis. But Elsevier charges $30 per article, and that is a bit steep for something that I might skim through once and then discard. Unfortunately, even after reading the abstracts it can be hard to tell which papers will turn out to be worth the expense and which ones won’t.

So, my simple request is that researchers take the time to upload papers to their web pages. I’m not sure what kinds of legal issues might be involved, but some of the articles that I did find online were also published in Elsevier journals, so I don’t think that copyright concerns are the main impediment. It may be more just a matter of developing the right mindset. So get those papers out there, and students and hobbyists everywhere will be grateful. (If copyright issues are the main problem, I’d like to hear more about that, too.)

1. D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, How easy is local search?, J. Comput. System Sci. 37 (1988) 79-100.

2. R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (eds.), Plenum Press, New York (1972), 85-104.

3. H. Kellerer, R. Mansini, U. Pferschy and M.G. Speranza, An efficient fully polynomial approximation scheme for the Subset-Sum Problem, J. Comput. System Sci. 66 (2003) 349-370.

4. G.J. Woeginger and Z.L. Yu, On the equal-subset-sum problem, Inform. Proc. Letters 42 (1992) 299-302.

Updates

Evidently Shiva Kintali would also like to see more papers uploaded to their authors’ web pages, and he would like to see it done really, really quickly!

Commenter BarrosH pointed out to me that Karp’s paper can in fact be found online, at Papadimitriou’s Reading the Classics course.

More Open Problems

July 12, 2007

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.

Carnival of Mathematics

July 2, 2007

I was just thinking to myself that it’s been a long time since I’ve seen a new Carnival of Mathematics, and sure enough when I checked the calendar I found that the 11th edition is now up at Grey Matters. Hmmm, none of the math/cs blogs I read regularly posted any announcements about this; how am I supposed to remember these dates on my own? Maybe everyone is on vacation this week.

Perhaps it’s just the summer doldrums, but this edition of the carnival seems a bit thin. There was a little bit of discussion back in the 10th edition about whether it might make sense to split into two separate carnivals: one for math ed and one for college and research level math. However, the current edition is almost all math ed, so perhaps the carnival will just evolve in that direction on its own. (There were also a couple of entries that really left me wondering what the authors were smoking, but that’s another matter.)

There was one entry that struck me as being worth mentioning, though. John Armstrong at The Unapologetic Mathematician writes about categorification: the process of recasting a mathematical abstraction into the language of category theory, as a means of solidifying one’s understanding of the topic. He gives some simple examples expressing addition and multiplication in terms of set operations, and reinterpreting the results in terms of category theory. As someone who doesn’t know anything about category theory, I find this both intriguing and mystifying. He concludes his post with the adage, “If you want to understand something, try to categorify it!” I think that I first need to understand categories, and Armstrong has a series of posts on the basics of category theory that might help me in that regard.

While we’re on the topic (sort of), I wonder if it would be worthwhile to try to split off the TCS-related posts from the Carnival of Mathematics into their own carnival? That might sound a little strange seeing as how there were exactly zero computer science posts in this edition, but I’m thinking that having our own carnival would encourage more submissions. Or is the TCS blogosphere so small (and we already read each other’s blogs anyway) that having a carnival would be superfluous?

 
Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org