March 20, 2010

Some time ago I had a question in my livejournal blog (in Russian) about books on project management. There I was given a nice advice to read The Goal by Eli Goldratt.

This turned out to be really interesting, one of the reasons of this being that in a steady way of a fiction book it discusses problems, that are quite familiar to those who know something about combinatorial optimization. Here you will meet some old friends like “Maximum flow” and “Two-route Johnson’s problem” (which seems to be much better known in Russia than anywhere else). However, they will look a bit different seen from the point of view of people who want to do all the optimization in real life. Probably some books on operational research and linear programming that can be found at any department of economics will give the same impression. Well, but reading a fiction book has its own fun anyway.

Do you know other fiction books that deal with algorithms or people who worked on them? Recently I tried to find some interesting autobiographies, memoirs or something about great computer scientists, but failed (well, in fact I found Bellman’s biography mentioned in Richard Lipton’s blog, but it seems to be impossible to get). Do they exist? Unfortunately, I don’t even expect these books to be as exciting as are books about Feynman for physicists.

Posted in Uncategorized |
4 Comments »

March 10, 2010

This is a post about an open problem that was given to me by Sofya Raskhodnikova last summer. The problem turned out to be rather difficult and I still don’t know the solution. Even on mathoverflow I got no answer about what methods to try. However, it can be described rather easily (you can see the description following the link to mathoverflow).

Here I will try to explain (very informally) what it has to do with algorithms and particularly testing monotonicity in sublinear time. I suppose that you have read the description of the problem.

Now suppose that we are trying to test a function for monotonicity using the following test: picking an edge of the hypercube at random and querying the values on its ends, if the edge is not monotone then we say “NO”, otherwise we continue the process. After some iterations we stop and say “YES”.

The problem is to prove that if the function is -far from being monotone then after small number of iterations we will find a non-monotone edge with high probability. Here -far means as usually with property testing problems that the minimal fraction of vertices at which the value of the function needs to be changed to make it monotone is . So we want to show that if there are many vertices, where the values need to be changed to make the function monotone, then there must be many non-monotone edges. Turning to contrapositive: if there are just a few edges then we can change values in a small number of vertices to make the function monotone. This is exactly what the described open problem is about.

Posted in Uncategorized |
4 Comments »

March 4, 2010

There are some books about algorithms that are not well-known in Russia (in my opinion), but still are really good.

One of them is “Randomized algorithms” by Rajeev Motwani and Prabhakar Raghavan. It is rather easy to read, but describes a lot of important ideas and is fairly well-written (as is another more famous book by Motwani et al. Introduction to Automata Theory, Languages, and Computation). It’s a great loss that Rajeev passed away several months ago and we won’t be able to see more exciting books written by him.

Posted in Uncategorized |
2 Comments »