Programming competitions are much easier if you have a good mathematical background
I went to school when I was five, though that was not my intention. My mother just thought that I got bored at kindergarten. My first school specialized in French, so I’d been learning it for quite some time. Later, my mother decided that I need to focus on mathematics, so I went to a study group at the Mathematical Center of the Presidential Physics and Mathematics Lyceum №239. I did quite good, so in the end, I transferred there and abandoned my French studies.
When I went to 9th grade, my mother decided that programming is the future and I have to brush up on computer science. As I wasn’t really good at it then, I understood that I have to go to the Summer School of IT. In order to pass the entrance examinations, I had to study individually with my computer science teacher, and I only made it to the D group. Still, it was the year when they made it possible to transfer to the C- group, where I could build up the necessary knowledge.
After that, I joined a programming club at ITMO University, and the next year, I made it to the group A- at the Summer School of IT. I think what helped me do that was a keen knowledge of maths. During my 10th grade, I made it to the All-Russian Competition in Mathematics. This also helped me with computer science, as solving programming tasks is easier if you have a good mathematical background.
Dropping sports programming and finding oneself in science
I graduated from school when I was 15, and at that time, I didn't really know what I was going to do. I had to choose between going to the Faculty of Mathematics and Mechanics of the St. Petersburg State University and ITMO University, but in the former case, it wasn’t clear what to do after, whereas with ITMO University my prospects were quite obvious. What’s more, during my time at ITMO’s programming club, I got to know Pavel Mavrin (tutor at the Information Technologies and Programming Faculty -- Ed.), and liked the overall atmosphere of the place.
Having joined ITMO University, I neglected research for quite a long time. All the way to my third year as a student, I had been doing sports programming; I started with Niyaz Nigmatullin (tutor at the Information Technologies and Programming Faculty, two-times champion of ICM ICPC – Ed.). Still, as opposed to those who spent their whole time training, I practiced a different approach: I never focused on sports programming only, and attended all lectures and did all the homework. At some point, I simply burned out and didn’t go to the finals; in the end, they just made me a member of the jury.
I’d say that my first step towards science was my Bachelor’s thesis that focused on calculating the adjacency matrix of a rectangular graph. In essence, that was about pure mathematics. During my Master’s years, I decided to continue doing research in this field and develop this topic even further. We did two articles based on my Bachelor’s thesis, then a couple based on my Master’s, and finally brought the research to a logical conclusion.
It was also the time when I got interested in concurrent programming. During my third year, we had lectures by Roman Elizarov (developer of the Kotlin programming language, expert in the field of concurrent programming and tutor at the Information Technologies and Programming Faculty – Ed.), and I liked the idea of network computing. And on my fifth year at ITMO, Umut Acar who was giving a course at the university told us about concurrent data structures. At that time, he was looking for a PhD student, so I thought: why not? And this is how I joined a PhD program.
Defending a PhD thesis in France
At that time, Umut Acar worked in France at INRIA, a national research university that focuses on computer science, control theory and applied mathematics. He invited me to work for him, and the Computer Technologies Department wanted to organize a joint PhD program. This wasn’t very easy, as INRIA is not a university is a common sense, they can’t give you a diploma. That’s why I had to register at a different university. In the end, we’ve succeeded in launching a joint PhD program with Paris Diderot University.
Studying on a PhD program in France had a lot in similar with how we once had it here. No one really supervises you: you can focus most of your time on your project. Because of that, the three years that I had been doing my research, I spent eight months a year in France only only four in Russia.
Still, I had my share of problems: before long, I had to change my research advisor, as he left for the USA, and working in such conditions isn’t easy. So for the most part, I had to work on my own. Then, I met Petr Kuznetsov (professor at Télécom ParisTech, ITMO University graduate -- Ed.), with whom I decided to continue my work. For this reason, I had three research advisors at my thesis defence: Professor Anatoly Shalyto from ITMO University, Petr Kuznetsov, and a professor from Paris Diderot University.
Wait-free data structures
It’s quite interesting that during our work, Petr Kuznetsov set me a task that has been around for about 20 years already. On the whole, it has to do with the question of whether it’s possible to develop a system where each process completes the operation in a finite number of steps.
Just imagine: there are processes, and each does its operations. So, what can happen? A process wants to add an element, but some other always comes forth, and it just can’t. This is not a wait-free system. A wait-free system is when something helps the process and adds it prior to itself. There already a method for doing that by using the compare-and-swap (CAS) operation, which is applied in most processors. Still, a question remains: what if we were to use something even simpler? Different researchers have been working on this task for 20 years already, and there is still no result.
What’s the point? By all accounts, it would’ve been great if all data structures were wait-free. Otherwise, the process stalls, it doesn’t move on and we can’t predict how much time it would take: ten minutes or an hour. Such predictions are most important, for example in nuclear plants where everything has to go according to a strict schedule.
Optimization of data structures and decrease in synchronization: how can concurrent computing help speed up different processes
In my PhD thesis, I achieved several major results. On the whole, my work involved five different parts. The first one that I worked on with my first research advisor was dedicated to concurrent computing. What this was about? There is such an operation as Fork/Join. It implies that we have two tasks, and we can do them concurrently. Surely, we can execute them sequentially, but we won’t benefit from that. So, it will be only logical to use Fork/Join.
The problem is that every operation takes time, so it’s important to identify the tasks you’d want to use Fork/Join for. Let’s say you have two small tasks that you want to launch concurrently: using Fork/Join can easily take more time than executing them sequentially.
I focused on developing a method that can automatically tell which would be the better way to go. Why would one need that? Everyone uses Fork/Join in their programs, as concurrent programming lets you make everything faster.
The other parts of my work were dedicated to the task of optimizing various data structures. For example, I worked on optimal search trees, with the purpose of accelerating these data structures. What is the point of doing that? Adding information to a data structure in a concurrent manner can lead to many mistakes. For instance, operations can overlap, and new data will be written over the recently added one. This is why you need to synchronize the processes, so that they would wait if necessary. I searched for ways to bring this synchronization to a minimum, which is a fundamental task that can be applied in many different fields, for example search engines.
On the knowledge of foreign languages
The knowledge of French that I got from school was of some help during my defense. Surely, I went to some courses before going to France, as I needed to brush up on my spoken language, as all I remembered from school was how to read texts.
During my defense, one of the board members told me that if she continued to talk in English, I probably wouldn’t understand her, and asked me a question in French. In the end, I answered it in French, as well, and they wrote in my defense results that I answered well in both English and French.
Nevertheless, I still think that knowing English only is enough for communicating with the scientific community and participating in various conferences and summer schools. Even in France, most young people have a keen command of English, especially those who are part of the scientific community.
Future prospects
As of now, I have to deal with my documents. I’m planning to go to Austria as a postdoctoral research fellow, and I’ve already negotiated it with Dan Alistarh from IST Austria. He works on most interesting things in the field of data structures, but I am going to focus on machine learning. I know that this topic is very popular with scientists, but I want to study concurrent machine learning in particular.
Explaining what it’s about is quite easy. Machine learning has to do with a process when we teach a network in a sequential manner. And now, let’s imagine that it would become possible to teach it concurrently. How can we speed up its performance, if we have many cores, 60, for instance? We need to come up with algorithms that will allow to process data as quickly as possible. Ideally, by the number of times equal to the number of cores we have.
Surely, that is not possible. I believe that getting a 20-times increase when using 60 cores will already be a progress. I’ll be working on the basic algorithms of machine learning, the gradient descent, for instance, which I want to make concurrent. What’s more, I will also be working on decreasing synchronization in existing machine learning algorithms.
Why doing research is more interesting than working for Facebook
Ever since my school days, it was the opportunity to program particular mathematical ideas that I liked in programming. Much like in science: you get some idea, for instance how you can optimize something with a particular algorithm, and then you bring it to life. When you’re working as a programmer at some company, what you do is mostly about program maintenance, doing simple things rather than coming up with complex algorithms.
I’ve had my experience of working for the industry: I spent a year working for Mail.ru and did a three-month internship at Facebook. But that was not my greatest venture. Surely, the offer good pay in the industry, but to my mind, this is the only advantage. The tasks given at companies are not very interesting; what is more, you don’t get to choose the tasks you like. Sometimes, you can get lucky, and work on an interesting project, but for the most part, you won’t. At Facebook, for instance, I’ve been doing nothing but rewriting a file from one format to another for over a month. In science, however, you can come up with something new, and advance the field you’re working in. Coding for someone other than myself is boring, so I prefer to work on my own ideas.
