Tuesday, October 31, 2006

Rather, it's been a big week for crystals

I mentioned some new results on crystals a short while ago; and today, there are two more. These are are of even greater interest to me, as they naturally follow my contribution to the program on perfect crystals.

The next step in M. Okado's research is to obtain an explicit description of type $D_n^{(1)}$-crystals. Since I have more experience dealing with such objects than just about anyone else, Okado-san has invited me to join him in Osaka to work on this problem. I'm not sure if I'll be able to make it, but the invitation certainly is tempting.

Thursday, October 26, 2006

IP $\neq$ LP

And in case you might have heard otherwise, we still don't know about P and NP. There are some recently submitted papers (all of which are rather light on references) in the Computational Complexity section of the CS arXiv claiming that P and NP are the same thing, based on formulating the traveling salesman problem as a linear program. Of course, they all make the classic mistake of underestimating the importance of constraining the variables to be integers.

The traveling salesman problem (or the TSP, an abbreviation that reduces the running time of saying its name by a factor of 2) asks simply "What is the shortest journey that makes exactly one stop in every city on a list?" Lest you think this problem is hopelessly academic, peruse this description of a few of the applications of the TSP. And lest you think that this problem seems simple, consider that $1,000,000 rests on its resolution.

I suppose it's not too shocking that a glory-seeking Associate Professor and an unknown researcher (is he a graduate student? an employee of a call-center software company?) would throw their hats in the ring. Hopefully they will learn that integer programming (IP) is not the same thing as linear programming (LP).

Fortunately, R. Hofman has set the record straight. Now, will those other two fellows follow the directions for withdrawing a paper from the arXiv?

Update 11/3/2006: R. Hofman has composed a more general rebuttal to those authors that have used linear programming to claim that P=NP.

Wednesday, October 25, 2006

A big day for crystals

Two papers just went on the arXiv dealing with crystals for generalized Kac-Moody algebras. None other than M. Kashiwara is involved in this project, so it must be big.

Oh, and there's this one, too. I think I know the author from somewhere.

Wednesday, October 18, 2006

Entropy always increases

And that goes for information too, of course. We all should be used to this phenomenon by now; whenever a scientific opinion or study is released, the press mangles it terribly, especially with its attention-grabbing, copy-selling headlines. It should come as no surprise that when a news source simply relays stories of interest to a niche group, there may be an additional loss of fidelity.

For example; there's a nice story on CNN reporting on a study from the Brown Center that shows a negative correlation between a nation's average math performance and its average enjoyment of and self-confidence in mathematics. And somehow, the esteemed editors have transformed this into a statement about people skills. (Update 11/6/2006: added link)

I would like to conclude, with overwhelming sarcasm, that slashdot editors have great confidence in and derive great pleasure from their ability to read a news story closely. But that wouldn't really be part of the solution, now would it?

Monday, October 16, 2006

Discrete topology

Of all the things that the title could mean, such as defining every singleton subset to be open, or discretizing the continuous as A. V. Evako does, this is by far the best I've ever seen.