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.

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):