Carlos Domingo - Un poco de todo

In the recent International Congress of Mathematics host in Madrid, Spain, the International Mathematical Union (IMU) awarded the Field Medals, what is considered to be the Nobel prize of mathematics (for a very interesting discussion about why there are no mathematics Nobel prizes read this article), and this was all over the news because of the rejection of the award by Grigori Perelman (I think that the fact that IMU still awarded him with the prize even knowing that he was going to decline it was pretty good and talks a lot about how mathematicians still appreciate science and not just politics).

Another prize that was awarded and that is a lot more relevant for today’s Internet was the Nevanlinna Prize that went to Jon Kleinberg for his work on Web organization and search engines through his theory of hubs and authorities, something consider an alternative/inspiration to Page Rank. Wikipedia claims that his algorithm is not commonly implemented in commercial search engines due to computational issues (part of the innovation that Google did with PageRank was not only on coming up with the ranking mechanism but showing how it could be calculated in an computationally efficient way, something that is not obvious when you are dealing with the massive size of the Web and given the fact that Page Rank is a recursive definition). I sort of remember that the hubs and authorities concept was actually used somewhere commercially so a bit of Web research pointed me to this other Wikipedia article that talks about Teoma, the search engine that now powers ask.com (which I have started to use more and more often, I think that they are doing pretty cool thinks, same goes for Amazon’s A9, btw, can someone tell me why A9 is called A9?) and how the ideas for that search engine started at the IBM project Clever which Kleinberg worked on and where his paper was originally written (btw, it is funny to see how researches still use Tex/Latex and generate PS files instead of PDFs).

I think that we will still see more innovation in search technology coming up in the next few years so we need more Jon Kleinbergs out there. The reason I think this is that search is still largely an unsolved problem in many respects. Just do a simple test, ask someone on the street “search engines” and the answer will be most of the time Google, Yahoo! and perhaps MSN search. Well, do a search for “search engines” in Google and you can see that Google cannot even recognize itself as a search engine in the first search results (see screen shot above) and the same search in Yahoo! (screen shot below) does better since it lists search engines but none of them is Google or Yahoo! (so they cannot also recognize themselves).

CD

Share on Facebook

This week I had a chance to spent some time with my former professor from the Tokyo Institute of Technology, Osamu Watanabe. It is funny that I ended up seeing him here in Barcelona after not seeing him at all the last few years that I was in Tokyo a lot more often.

He explained me an anecdote about how he thought that Sudoku meant “numbers poison” since you could actually write it that way using Japanese kanji and how he told so an American that he met on a plane trip that was playing Sudoku. In fact, Sudoku is not written with the kanji for “number” (su) and “poison” (doku) but numbers and “single” (doku means also poison but with a different kanji) and as explained in this article, the game, not invented in Japan but in the US and popularize by a Japanese magazine under the new name which was trademarked (the game itself cannot be patented or trademarked) was originally referred to as “suji wa dokushin ni kagiru,” which means “the numbers must be single”—meaning not repeated. The name was then shortened to Sudoku, which means “single numbers.

Watanabe-sensei is working with one of his student on trying to solve the problem of providing a way to enumerate Sudoku problems. As far as he knew (and few Internet searches confirmed this in an extremely experimental way), this problem has not been solved, what has been solved is counting how many Sudoku problems are out there.

Solving this problem and providing an algorithm for generating a unique number for each Sudoku number will prove to be very popular since someone could easily create a centralize database of known Sudoku problems (just the numbers) and then check against that to see whether that one exists and then claim that number or someone could be challenged to create Sudoku problem number 234,934 knowing that someone else has already created problems 234,933 and 234,935 and fill the gap. Notice that since every Sudoku problem has a unique solution, what we are counting here are unique solutions but for each solution one can generate a lot of different starting points just by removing numbers differently. That also leads to the problem of how many numbers can you remove while leaving the problem solvable which is another interesting problem. Since Sudoku is basically a constraint satisfaction problem, as a theoretical computer scientists will say, it is a a very interesting source for mathematicians and theorists to study it. You can apply known computer science techniques like integer programming to solve it.

Finally, the article in the American Scientist has a short but interesting discussion about Sudoku strategies and whether you can solve it by pure logic (you always put a number in a place knowing that is the only number that can go there and that allows you to continue) or backtracking basically guessing till you arrive to a mistake and then go back to the initial guess and try with another one). I have always solved Sudoku problems by logic (which is in fact why I like Sudoku since using backtracking is not mentally challenging) so it will be interesting to know whether this is in fact the only way to solve them or there are problems where backtracking is absolutely necessary.

CD

Share on Facebook