Master in Theoretical Informatics, Academic University (RAS)

In St. Petersburg, there is a wonderful place where programmers make computer science theorists. This is the Academic University of the Russian Academy of Sciences (AU RAS).

At that time, when I entered the Theoretical Department of the Department of Mathematical and Information Technologies of the AU, the department had only one graduation, consisting of two people. Now the Academic University has already earned itself a wonderful name. Its graduates work in the leading companies of the city, it accepts students from other cities, providing them with housing, and a paid department costs only 10 thousand rubles per semester.
')
But I want to tell you, by my example, what interesting and deep problems you can explore and how many interesting things you can learn if you become a student of the theoretical department.

My research work at AU

At the theoretical department of AU is required to conduct serious research for writing the master's work. Managers are trying hard so that you have a publication at the same time - which is already very tempting.

My work was led by Dmitry Mikhailovich Itsykson (POMI RAS) and it was devoted to the study of optimal algorithms. This is a very interesting topic, and it is also remarkable because it is easy to explain, and I’ll try to do it now.

Motivation

Let's look at some NP- complete problem, for example, the language of executable formulas. We will consider algorithms that stop on any formula and return one bit as an answer - is the formula executable or not. For 40 years, the question has been asked whether there is a polynomial among this set of algorithms, and no one has yet been able to answer it. However, we can ask others, perhaps a simpler question, whether this problem has an optimal algorithm — an algorithm that runs faster than all the others up to a polynomial (since we are only interested in the polynomiality of the algorithms). Suppose that such an optimal algorithm exists (let's call it A ), then NP is not equal to P if and only if A is not polynomial. This is already something, since we need to prove the non-polynomiality of one particular algorithm, instead of doing it for all possible algorithms that solve our problem.

Let's look at another example - on co-NP, a complete task, for example, the language of tautologies (everywhere valid formulas). There is a large number of evidence systems for tautologies: the resolution method, the system of cutting planes, the Frege system, etc. The question of the existence of a system of evidence that would have proofs of polynomial size is equivalent to the open question of the equality of the classes NP and co-NP . In fact, it is surprising how many people are engaged in comparing specific evidence systems and finding lower scores for them. It would be great to have an optimal evidence system, then it would be enough for us to study it alone.

So, both of these questions served as a motivation for the study of optimal algorithms for my master’s thesis and we got something really interesting in this direction.

Previous studies

A year earlier, D. Itsykson and E.A. Hirsch proved the existence of an optimal heuristic probabilistic semi-algorithm for any enumerable language, where

• semi-algorithm — half-resolution algorithm — an algorithm that responds to 1 at the inputs from a language and does not stop at other inputs
• probabilistic - the algorithm has access to random bits (it can throw a fair coin)
• heuristic - the algorithm can make a small (limited) error, and this error can be made as small as desired by increasing the running time.

Naturally, we would like to build an optimal algorithm for a weaker computation model. Firstly, we would like to get rid of the error that the algorithm gives, and secondly, to make it not probabilistic, but deterministic. The last transformation is called derandomization, and there are more or less standard methods for this. I was offered to try to implement them.

results

Instead of using random bits, you should try to extract randomness (entropy) from the input (since there is no other place). This can be done using a bipartite “mixing” graph (something like lookup table), where in the left part we will be indexed by the input, and the set of adjacent vertices from the right part will give us a set of pseudo-random bits.

After the first attempt to formulate the necessary conditions for the graph, we realized that in the general case it was not possible to do this, so we decided to consider a simpler case - the language of the set of images of an injective function that increases its input by one bit. Here, the reader (if there are readers who got here) should receive legitimate indignation: “who are interested in such languages”? However, suppose we are interested in a pseudo-random generator (the existence of provably reliable injective generators that increase their input by one bit is an open question). Then we will get the optimal algorithm, which will say: “is it true that the given (him) number was generated by our generator”? If this optimal algorithm turns out to be polynomial, we will “break” the generator, i.e. we will distinguish the numbers he spawns from the truly random! It would be really very cool, because we would find attacks on almost all existing cryptosystems.

So, in this case, we succeeded in derandomization and moreover, we built not only the optimal heuristic semi-algorithm, but added it to the full algorithm.

My research has ended with an article and a great desire not to leave the wonderful field of theoretical computer science, where there are still a lot of open questions and unsolved problems.

Five reasons to go to the AU Magistracy ...

... if you want to study theoretical computer science:

1. AU is the only place in St. Petersburg and one of the few in Russia where you can devote yourself to the study of theoretical computer science.
2. In AU work energetic and undoubtedly talented scientists.
3. In AU, students can influence the curriculum and choose part of the courses as they see fit.
4. AU sponsors trips to schools, including foreign ones.
5. In AU, you will find free coffee from a wonderful espresso machine! (so that was what to process into theorems).

What do I do after the end of the AU?

I continue to do theoretical computer science at Stanford. In the previous quarter, I was involved in computing on encrypted data with Dan Boneh, and now I’ll deal with circuit complexity with Ryan Williams.

So, my advice - go ahead, it's worth a try! You can apply now.