Hey. This post is a kind of an advertisement for the MIT course 6.080 (thanks to overrider for the link). I strongly recommend everyone who has any interest in computer science to read the lectures. Course covers a lot of awesome topics like Turing machines, computability, reducibility, quantum computers, completeness and incompleteness theorems and many more. Of course, if you are quite an awesome computer scientist, you’ll hardly find anything you haven’t heard before in the course. But I believe that almost anyone can find something interesting there. Now I’d like to share some facts from the lectures with you to interest you more.

You almost certainly know that some problems are undecidable. Classic example of such a problem is a halting one. But how many problems are undecidable? Only this one? Or, may be, this one and six hundred other? Is the number of undecidable problems even countable? Well, it turns out that it’s not. While there exist countable number of algorithms (one can easily prove it by sorting programs written in some Turing-complete programming language in lexicographical order), set of possible problems has the cardinality of the continuum (proof of this fact is quite simple, it’s almost like the Georg Cantor’s proof that the set of the real numbers is not countable). So, decidable problems are like a drop in the ocean.

Other interesting fact can be proven. For any possible computational complexity (n^2, n^(n! log n) etc) there exists at least one problem for which algorithm with such complexity is the best one. That problem is “does given algorithm accept given input in no more than K steps” and it can’t be solved faster than in O(K) by actually running the algorithm.

Problem “does given statement have a proof of length N or less” is in NPC. So, if P=NP, we can choose reasonably big N and check for the existence of the proof (relatively) quickly. If there is no proof of reasonable length, we can conclude that problem is not of any interest. So, in fact, if P=NP, we should stop paying mathematicians for proofs because machines can probably do better. Unfortunately, nowadays almost everybody is quite certain that P is not equal to NP.

Another interesting topic is derandomization. Does every randomized algorithm have a corresponding deterministic algorithm? Recent success in the proof that PRIMES is in P is closely related to this question.

If the facts mentioned above make you excited, you should totally read the scribe notes. I’m out.

“Structure methods for image and signal analysis” course at our CS department is getting nicer and nicer. Last week we have Vladimir Kolmogorov invited, talking about techniques for energy minimization in complex graphical models. This week Victor Limpitsky will give a talk named “Image Segmentation: beyond Graph Cuts”. Btw, if you are interested in this course, slides from all the lectures are available here (unfortunately, in Russian language only).

Funny observation: it seems that Vladimir hadn’t been giving math talks in Russian for a quite long time. His Russian is still perfect, but he doesn’t remember even Russian equivalent for “limit point” or “real number”. He asked people who was sitting in front of him to translate various math words from English into Russian during the whole talk.

Btw, have you heard about Logicomix? It’s a comic book about Bertrand Russell, famous logician and mathematician. It covers a lot of interesting stuff including introduction to intuitionism and formalism, Russell’s connections with Kurt Gödel, Henri Poincaré, David Hilbert and other legends of mathematics. And all that great stuff is available in a nice form of a comic book, both online and in hardcover.

Currently there is an interesting problem at the TopCoder Marathon Match. Given a set of 2D points, your task is to enclose all the points with at most M circles and to minimize the total area of all the circles used. Apparently, this problem has no straightforward optimal solution, so various discrete optimization techniques have to be involved. We’ve tried evolutionary optimization yesterday, but we haven’t succeeded yet. More good ideas need to be involved =)

Forget to mention. I’m going to spend significant part of the next two years of my life in the computer science and data analysis school hosted by Yandex together with MIPT. Of course, my primary objective is to learn a lot of new cool stuff about machine learning, optimization theory and discrete math. But the other important thing is that I will definitely meet some new awesome people there. So, you know, it’s probably gonna be quite interesting.

Btw, really great people like Albert Shiryaev and Alexey Chervonenkis will lecture there. That’s someting I can’t miss.

This week I have visited a few lectures of the Microsoft Research guys during the Microsoft Research summer school on high performance computing at MSU. There were a lot of interesting stuff at the school. The main idea behind the school was that Von Neumann architecture is too old and its limitations become more and more obvious. So, computer science field (its programming part especially) must be “reinvented” soon. As an alternative to the classic imperative programming, MSR guys propose using functional languages like Haskell. So, they have talked about Haskell (and, especially, about parallel programming in Haskell) a lot. And, of course, Simon Peyton-Jones, one of the main developers of the Haskell language and lead designer of the Glasgow Haskell Compiler, was there. He is very inspiring and cheerful man, and his talks are really great! But the talk I liked most was not about functional programming. It was about research papers and talks (it was kind of a meta talk). Slides and other stuff (like videos) related to that talk are available here, but I’m still going to list some of the major (or just interesting to me) theses:

1. Writing articles and giving talks is not about anything but sharing ideas.
2. Have an idea (it’s not necessary for your idea to be a fantastic one) => write an article.
3. One article <=> one clear idea.
4. Use a lot of examples! Every definition or statement (especially the one with complicated math) becomes much more clear if it has an associated example.
5. Related work section should be placed just before conclusion. Other works can distract your reader from your (good or not) own work (this idea was quite surprising to me).
6. Be as clear and concrete, as possible.
7. Write in active voice, use agents (like process, algorithm, iteration etc). For example, “this algorithm selects best classifier” is much better than “best classifier is selected”.
8. Good talk contents: motivation (20%) and key idea (80%).
9. You should select something you want your readers to remember after listening to your talk. Concentrate on that thing. It’s absolutely normal to cover only part of your paper at your talk.
10. Adding outline to your slides makes no sense but wastes the time of the talk.
11. Again, examples are your main weapon!
12. Do not show the total amount of slides to your audience (numbers like “6 of 95” can make people very sad).
13. Always finish in time. And it’s better to save some time for questions than to show all the slides to your audience.
14. Be enthusiastic! Do not make excuses! Do not afraid to be afraid of your talk (everybody does)!

I hope reading this will help someone with his (or her) paper or talk. And I hope that person will look through the original slides or watch the video by himself. It is worth all the time spent.

Few days ago Microsoft Research with the help of Bill Gates launched a special Web site where everyone can have access to the lectures of my (as I already mentioned) favorite physicist Richard Feynman. Curtis Wong, member of the MSR Next Media Research Group, have developed a special presentation approach for that lectures. Tuva video player supplies you with notes, hyperlinks and interesting information during the lecture and allows you to make your own notes in it. Actually, it forces you to learn new stuff! I’m pretty sure Feynman would have liked this way of education.

So, check out this amazing project - enjoy tuva!

Last few month I was participating in the NVidia CUDA lecture & seminar course hosted by the NVidia company together with CMC department of the MSU. NVidia offered certificate to every participant who will successfully solve all the proposed assignments or use CUDA in his (or her, I’ve seen some girl who did it) course project. There were no place for CUDA in my course project (at least, I though so), so I’ve written the following 5 programs in C++/CUDA.

1. Find all the roots of the piecewise-linear function with A LOT of points. It was the first and the most simple one.
2. Calculate haar wavelet coefficients for the 1D signal.
3. Implement simple real-time raytracer with support for planes, spheres and triangles (also with texturing).
4. Numerical heat equation solution.
5. Optimization of a given a program that performs image filtering using convolution with large kernel.

Need to say, some of this assignments were quite interesting. Problems that have pretty simple general parallel algorithm can be very hard to implement on stream computing architecture efficiently. Anyway, performance boost worth it.

So, now I’m happy owner of that piece of paper (blame Steve Jobs for the bad iphone camera quality):

Today I’ve visited an interesting event - Freeman Dyson’s lecture at the Lebedev Physical Institute of the Russian Academy of Sciences. Dyson is American physicist and mathematician, famous mostly for his work in quantum field theory, but also for some very interesting and provocative thoughts about science, religion, life and everything (today he said something like “I’m too old for science, but young enough for philosophy”). Many of his ideas are about our future: look at Dyson sphere or Dyson tree. But today his lecture was related to global warming, nuclear weapons and genetic engineering.
Here is a short list of what I’ve learned today:

• Dyson thinks that genetically modified plants can solve all the problems with global warming. Some people say that’s crap but who knows? I’m not a specialist.
• There probably was a quite long pre-evolution period when simple life forms (consisting of a few self-replicating moleculas) shared their advantages to each other (like in open source) to improve life quality and become more sophisticated organisms.
• 6 thousand years ago there were a lot of lakes and trees in Sahara. And if global warming will strike, trees and lakes can come back.
• Genetic engineering can become for us something like computer games in the future. Imagine a genetic game when you should grow the most powerful lizard in a week. Sounds great, but a bit strange.
• Nuclear strikes were not the reason Japain surrendered in WWII.

There was a lot of other amazing stuff, but I’m just too lazy to post it there. It’s much more better to listen him, than to read about it here. He worked with Albert Einstein and my favorite physicist (do you have a favorite physicist?) Richard Feynman, btw.